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ő.
- 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
- 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
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
