<p>I am looking for a detailed list of known reductions of NP-Complete problems. Much like Richard Karp's list of 21 NP-Complete problems has more than a dozen reductions, I am looking for a bigger database. Is there such a database? If not, where can I find known reductions along with citations?</p>

CC BY-SA 4.0
2023-07-28T13:20:24.963Z
There is no such database. Hundreds of NP-complete problems have been identified in hundreds of papers, and they are not maintained in any central repository. If you are interested in a particular problem, search the literature on that problem.
Emil Jeřábek
CC BY-SA 4.0
2023-07-28T16:33:21.887Z
You might be interested in the answers to this question: https://mathoverflow.net/questions/408250/is-there-a-website-or-a-survey-collecting-all-np-complete-problems-on-graph-theo
domotorp
CC BY-SA 4.0
2023-08-06T02:01:02.333Z
There's Garey and Johnson's book *Computers and Intractability: A Guide to the Theory of NP-Completeness.* This has a long list of problems at the end (pp. 187–284).
Peter Shor 
<np-complete><db.databases>
I am looking for a detailed list of known reductions of NP-Complete problems
Andrija Sevaljevic
# I am looking for a detailed list of known reductions of NP-Complete problems

(Asked by: username_0 on 2023-07-28)

I am looking for a detailed list of known reductions of NP-Complete problems. Much like Richard Karp's list of 21 NP-Complete problems has more than a dozen reductions, I am looking for a bigger database. Is there such a database? If not, where can I find known reductions along with citations?

**Tags:** np-complete, db.databases
> **Comments:**
> **username_1**: There is no such database. Hundreds of NP-complete problems have been identified in hundreds of papers, and they are not maintained in any central repository. If you are interested in a particular problem, search the literature on that problem.  
> **username_2**: You might be interested in the answers to this question: https://mathoverflow.net/questions/408250/is-there-a-website-or-a-survey-collecting-all-np-complete-problems-on-graph-theo  
> **username_3**: There's Garey and Johnson's book *Computers and Intractability: A Guide to the Theory of NP-Completeness.* This has a long list of problems at the end (pp. 187–284).  

---

## 0 answers

