Re: basic query regarding NP Complete...

In article <1156569181.083044.321040@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Prakash <helloprak@xxxxxxxxx> wrote:
Is it also possile to have an entirely different set of problem, unrelated
to SAT ( or atleast not depending on SAT and its relatives ) to be NP
complete. Say start by proving a problem is NP and NP hard... and then
polynomially reduce it to other problems.

By definition, a problem in NP is NP-complete if *every* other problem in
NP can be reduced to it.

You could certainly pick some other problem and start reducing other
problems to it. However, if your other problem is NP-complete, then
*by definition* every other problem---INCLUDING SAT---must reduce to it.
So your tree will necessarily hook up with the SAT tree.

"Every other problem in NP" really does mean *every* other problem in NP.

There could, of course, be families of problems in NP that are *not*
NP-complete but that are polynomially reducible to each other. If P != NP,
there are necessarily other such families that are distinct from the family
of NP-complete problems.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.