Ecco alcuni dei più noti problemi che sono NP-completi quando vengono espressi come problemi decisionali. Questa lista non è assolutamente completa (sono noti più di 3000 problemi NP-completi). La maggior parte dei problemi in questa lista è presa dal fondamentale libro di Michael R. Garey e David S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness