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 NPComplete by reducing a known NPcomplete problem to it. Once we prove that a prblem 'A' is NPcomplete by reducing an NPcomplete 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 'nottheemptystring', 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):
Relevant Pages
