Re: basic query regarding NP Complete...

"Prakash" <helloprak@xxxxxxxxx> writes:

Hi,
I have am trying to understand the basics of NP and NP complete.
Can any one help me better my understanding.


Here is my query regarding the same

Do we call a set of problem in NP to be NP complete if each one of them
is reducible to an other ? ie.. if 3-CNF, Boolean satisfiability,
Vertex cover, Hamilton cycle.. problems form a set and each of them is
reducible to one of the other then do we call that set NP-Complete ?

Suppose I have a NDTM that solves the sorting problem by randomly
guessing the order and I have a verifier Algorithm (polynomial) that
outputs a YES if all elements are in order, This problem is in NP.
Supposing I have few other hypothetical problems that are reducible to
this problem will that set form a NP-COMPLETE set ? Since P is a subset
of NP do we have many partitions in class P that are reducible to each
other within that partition and hence NP complete ?

Please correct me if my understanding is wrong.

Thanking you,
Prakash S

Hi Prakash,

if a problem A is in NP it is called NP-complete if it is at least hard as all
other problems in NP. That means: SAT is NP complete (COOK's theorem) and all
other problems already known to be NP-complete (traveling salesman, 3-CNF,
....) regarding the following. Find a polynominal-time function f_A which maps
SAT's input to a representation of A's input (i write: SAT <=p A , which means
'SAT p-reducible A'). So each instance of SAT can be solved as instance of A.
It follows that A is as hard as SAT which implies A is also NP-complete.
Suppose you have shown that problem B is NP-complete
(B in NP -and- SAT <=p B).
Now you can alternatively try to show A's NP-completeness by showing
B <=p A (because: SAT <=p B <=p A implies SAT <=p A). If you now take a whole
set C of problems and you want to show NP-completeness of C, you have to show
that for each c \in C SAT <=p c holds.

I hope i could help you a little?

Kai
.

Relevant Pages

  • Re: Path from a walk in a graph.
    ... I have used GAs on proven NP-complete ... Alg> If a walk (a_1..... ... It seems that your understanding of NP-completeness ...
    (sci.math)
  • Re: basic query regarding NP Complete...
    ... initial problem needs to be NP-Complete (such as SAT proved to be one ... problems form a set and each of them is ... of NP do we have many partitions in class P that are reducible to each ... Find a polynominal-time function f_A which maps ...
    (comp.theory)