[Q]: List of all possible reductions between NP problems

From: "NPC" <moti_ba@xxxxxxxxx>
Date: 31 Jan 2006 09:03:36 -0800

Hi All,

We use reductions to prove that a problem is NP-Complete by reducing a
known
NP-complete problem to it. Once we prove that a prblem 'A' is
NP-complete by
reducing an NP-complete problem 'B' which is already known.....the two
problems will be in the same class.

For example:

SAT<=p CNF
CNF<=p Clique

Is there a web resource that explain in detail all the possible
polynomial reductions between the different problems?

Thanks,
NPC.

.

Follow-Ups:
- Re: [Q]: List of all possible reductions between NP problems
  - From: Bryan Olson

Prev by Date: Re: Induction problem ? (Atleast I think it is that :)
Next by Date: Re: Induction problem ? (Atleast I think it is that :)
Previous by thread: Induction problem ? (Atleast I think it is that :)
Next by thread: Re: [Q]: List of all possible reductions between NP problems
Index(es):
- Date
- Thread

Relevant Pages

Re: Question: List of all possible reduction between NP problems
... > reducing an NP-complete problem 'B' which is already known.....the two ... > polynomial reductions between the different problems? ... There are a lot of possible polynomial reductions. ...
(sci.math)
Question: List of all possible reduction between NP problems
... NP-complete problem to it. ... Once we prove that a prblem 'A' is ... reducing an NP-complete problem 'B' which is already known.....the two ... polynomial reductions between the different problems? ...
(sci.math)
Re: [Q]: List of all possible reductions between NP problems
... Once we prove that a prblem 'A' is NP-complete by reducing an NP-complete problem 'B' which is already known.....the two problems will be in the same class. ... polynomial reductions between the different problems? ...
(comp.theory)