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

*From*: Bryan Olson <fakeaddress@xxxxxxxxxxx>*Date*: Tue, 31 Jan 2006 20:24:59 GMT

`NPC wrote:`

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.

Almost. We have also have to show A is in NP.

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?

Of course not. If we could even determine the existence of a polynomial reduction from SAT to 'not-the-empty-string', we'd have an answer to P ?= NP.

-- --Bryan .

**References**:

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