Re: basic query regarding NP Complete...


"Prakash" <helloprak@xxxxxxxxx> wrote in message
news:1156569181.083044.321040@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
any instance of a known NP-Complete problem, like 3-SAT,
can be converted, in polynomial time, into an instance of "a",
an instance of "b", and an instance of "c". Then you can say X
is a set of NP-Complete problems.

I have a question here. Forgive me if I sound a little stupid.. I
wanted to know if NP-Complete consists 'ONLY' of SAT and other problem
related to it by 'polynomially reducable' relation. I suppose cookes
first proved that SAT was NP Hard and in NP and hence NP completed
?(correct me if I am wrong). And the tree started from there. 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.

Question in short... Why does it always have to start with SAT ?

The definition of NP-Complete requires that you be able to show any problem
in NP can be converted in polynomial time into the problem you are claiming
is NP-Complete.

Using SAT is probably the simplest way to prove another problem is
NP-Complete.
And you have to show SAT can be converted to prove the other problem
is NP-Complete. SAT doesn't have to be the "first" one, but you have to
prove it anyway, so why not start with SAT.


Russell
- 2 many 2 count


.

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: NP-complete and NP-Hard?
    ... > I don't quite understand NP-Complete and NP-Hard problem, ... NP is the class of problems that can be solved in polynomial time (in ... that you need exponential time to solve an NP problem - there might be ...
    (comp.theory)
  • 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)
  • 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)
Loading