PROFILBARU.COM

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

Jegyzetek

↑ (2007) „Algorithms for graphs embeddable with few crossings per edge”. Algorithmica 49 (1), 1–11. o. DOI:10.1007/s00453-007-0010-x.
↑ ^a ^b ^c ^d ^e ^f ^g Karp, Richard M.. Reducibility among combinatorial problems, Complexity of Computer Computations. Plenum, 85–103. o. (1972)
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5
↑ (Arnborg, Corneil & Proskurowski 1987)
↑ Minimum Independent Dominating Set

Fordítás

Ez a szócikk részben vagy egészben a List of NP-complete problems című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.