In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems.


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.

  • 1
    $\begingroup$ As a side note: There is an infinite number of $NP$-complete problems. Simply take your favorite $NP$-complete problem, and call it $L$. For any $k\ge 0$ we have that $0^kL$ is also $NP$-complete. Since we can choose an infinite number of $k$'s, we also must have an infinite number of $NP$-complete problems. $\endgroup$
    – nir shahar
    Oct 5 '21 at 22:25
  • $\begingroup$ Ahm yes...I've edited my question :) $\endgroup$
    – Algebruh
    Oct 5 '21 at 22:27
  • 3
    $\begingroup$ Though not containing the actual reductions, the standard reference is Garey & Johnson. $\endgroup$ Oct 6 '21 at 7:00
  • 3
    $\begingroup$ An interactive database of reductions similar to ISGCI would be pretty neat. If it doesn't exist, it might be a fun student project to make one. $\endgroup$
    – Discrete lizard
    Oct 6 '21 at 7:20

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.