patternMinor
Is there a book with 100 reductions?
Viewed 0 times
bookwith100reductionsthere
Problem
In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems.
Question:
I was wondering if there exists something like a database or a book with some known reductions (or with maybe more than only the NP-complete ones) and the proofs for them? I know there is a very nice database for Rings, but I couldn't find something similar for reductions.
Question:
I was wondering if there exists something like a database or a book with some known reductions (or with maybe more than only the NP-complete ones) and the proofs for them? I know there is a very nice database for Rings, but I couldn't find something similar for reductions.
Solution
The classical reference on NP-completeness is Garey and Johnson's Computers and Intractability, which contains a compendium of over 300 NP-complete problems, with links to papers proving their NP-hardness. The only downside is that the book is quite old, dating from 1979.
Context
StackExchange Computer Science Q#144508, answer score: 3
Revisions (0)
No revisions yet.