# Is there a book with 100 reductions?

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.

• 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. Oct 5 at 22:25
• Ahm yes...I've edited my question :) Oct 5 at 22:27
• Though not containing the actual reductions, the standard reference is Garey & Johnson. Oct 6 at 7:00
• 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. Oct 6 at 7:20