Re: NP-complete and NP-Hard?

yijun_lily@xxxxxxxxx writes:

> I don't quite understand NP-Complete and NP-Hard problem, eventhough I
> read some books about algorithm. Can anybody tell me about them?
>
> Is NP-complete and NP-Hard problem a problem that can't be solved in
> polynomial time (i.e.)?

In simple terms, a nondeterministic machine can spawn a new machine
every time it needs to make a choice, so after n choices, there can be
2^n machines. These machines can not communicate, but if any one
stops with an answer to the problem they are given, we say the problem
is solved.

NP is the class of problems that can be solved in polynomial time (in
terms of input size) on such a nondeterministic machine.

If you use a deterministic machine to simulate a nondeterministic
machine, you need to simulate all the spawned new machines on the same
machine. Since the number of machines can increase exponentially,
such simulation takes exponential time. However, this doesn't imply
that you need exponential time to solve an NP problem - there might be
a deterministic program that can solve the problem in another way.

This is the essense of the P = NP problem: Are there NP problems that
can not be solved in polynomial time on a deterministic computer?
This is as yet unanswered, though many suspect that P != NP.

A problem being NP-complete means that the problem can be solved in NP
and, furthermore, that any NP problem can be translated into this
problem in polynomial time. So if any one NP-complete problem can be
solved in polynomial time, all can.

NP-hard means that you need at least NP to solve the problem, but
maybe more. It means that any NP problem can be translated to this
problem, but the converse may not be true.

So NP-complete \subseteq NP \subseteq NP-hard.

Many interesting problems, including code breaking, is in NP, so it is
interesting to study efficient ways of solving these.

Torben

.

Relevant Pages

  • Re: Consecutive Numbers
    ... NP problem is said to be NP-complete if the>existence of a polynomial ... footing--- if any one of them can be solved in polynomial time, ... to be non-P or NP>"Finding the prime factors of a given integer is ... it does, then factorization, which is certainly in NP ...
    (sci.math)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... Radoslaw Hofman wrote: ... If there is a UP set that is NP-complete, ... he may solve any TSP instance in polynomial time then he can solve any ... (unique solution and polynomially solvable) ...
    (comp.theory)
  • Re: On NP Completeness and Intractability
    ... An NP-Complete problem is proven to be in NP, ... > an NP-hard problem in not proven to be in NP (it might or it might not be ... >> 3) If a polynomial time algorithm is discovered for a hitherto NP-Hard ...
    (comp.theory)
  • NP-Complete Definition
    ... If B is NP-Complete and B is polynomial-time-reducible to C (where C ... Suppose that the reduction R reduces B to C in polynomial time, ... Maybe the original input to B was of size n, ... The reduction occurs in polynomial time, ...
    (comp.theory)
  • Re: basic query regarding NP Complete...
    ... is a set of NP-Complete problems. ... Forgive me if I sound a little stupid.. ... I suppose cookes ... in NP can be converted in polynomial time into the problem you are claiming ...
    (comp.theory)
Loading