Re: Question: List of all possible reduction between NP problems

moti_ba@xxxxxxxxx wrote:
> 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.

There are a lot of possible polynomial reductions. There are hundreds
of known NP-complete problems and between any two of them there exists
a reduction. In most cases no one has every explicity written down
that reduction, but they must exist.

So no, there is not a web resource that explains in detail
all the possible polynomial reductions. There are far to many
of them. In theory, there are an infinite number of possible
polynomial reductions.

The Garey and Johnson book "Computers and Intractability" contains
the descriptions of a hundred or so NP-complete problems and includes
references to the papers in which they were first demonstrated to
be NP-complete.

Stephen
.

Relevant Pages