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 Az irányítatlan gráf klikk-problémája A körlefogó csúcshalmaz problémája A minimális lefedő csúcshalmaz probléma Faszélesség meghatározása Feszített út problémája Függetlenhalmaz-probléma Gráfszínezés, a kromatikus szám problémája Gráfhomomorfizmus-probléma: van-e két adott gráf között gráfhomomorfizmus Irányított vagy irányítatlan gráfban van-e Hamilton-út vagy -kör Kínaipostás-probléma irányított és irányítatlan éllel is rendelkező gráfokra. (Polinomidőben megoldható, ha csak irányítatlan vagy csak irányított élek vannak.) Legkisebb maximális független csúcshalmaz meghatározásaMinimum Independent Dominating Set Legkevesebb élet tartalmazó maximális párosítás meghatározása Teljes színezési probléma, az akromatikus szám meghatározása
Matematikai programozás
Boole-hálózat kielégíthetőségi problémája A 3-SAT probléma Részletösszeg-probléma Az utazó ügynök problémája Hátizsák-probléma Kvadratikus programozás Járműútvonal-tervezési probléma
Jegyzetek
Fordítás
Kategória:Számítási bonyolultság Kategória:Matematikai listák