NP-teljes problémák listája

Ez a lista néhány ismert NP-teljes problémát sorol fel. Az NP-teljesség számítástudományi fogalom: informálisan fogalmazva az NP-teljes problémák olyan NP-beli problémák, amikre bármely más NP-beli probléma visszavezethető.

Gráfelmélet

• 1-síkbarajzolhatóság eldöntése^[1]
• Az irányítatlan gráf klikk-problémája^[2][3]:GT17
• A körlefogó csúcshalmaz problémája^[2][3]:GT7
• A minimális lefedő csúcshalmaz probléma^[2][3]:GT1
• Faszélesség meghatározása^[4]
• Feszített út problémája^[3]:GT23
• Függetlenhalmaz-probléma^[3]:GT20
• Gráfszínezés, a kromatikus szám problémája^[2][3]:GT4
• Gráfhomomorfizmus-probléma: van-e két adott gráf között gráfhomomorfizmus^[3]:GT52
• Irányított vagy irányítatlan gráfban van-e Hamilton-út vagy -kör^{[2][3]:GT37, GT38, GT39}
• Kínaipostás-probléma irányított és irányítatlan éllel is rendelkező gráfokra.^{[3]:ND25, ND27} (Polinomidőben megoldható, ha csak irányítatlan vagy csak irányított élek vannak.)
• Legkisebb maximális független csúcshalmaz meghatározása^[5]
• Legkevesebb élet tartalmazó maximális párosítás meghatározása^[3]:GT10
• Teljes színezési probléma, az akromatikus szám meghatározása^[3]:GT5

Matematikai programozás

• Boole-hálózat kielégíthetőségi problémája^[2][3]:LO1
• A 3-SAT probléma^{[3]:p. 48}
• Részletösszeg-probléma^[3]:SP13
• Az utazó ügynök problémája^{[3]:ND22, ND23}
• Hátizsák-probléma^[2][3]:MP9
• Kvadratikus programozás
• Járműútvonal-tervezési probléma