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
[szerkesztés]- 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
[szerkeszté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
[szerkesztés]- ↑ (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 i j k l m n 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
[szerkeszté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.
|
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |