Lista problemów NP-zupełnych
Logika[edytuj | edytuj kod]
- Problem spełnialności (SAT)
Problemy grafowe[edytuj | edytuj kod]
- Problem znajdowania cyklu Hamiltona
- Problem znajdowania kliki w grafie
- Problem komiwojażera (COMI)
- Problem znajdowania pokrycia wierzchołkowego
- Problem trójkolorowalności (3COL)
- Kolorowanie grafu
- Cykliczne pokrycie krawędziowe
- Problem zbioru niezależnego
Problemy podziału zbioru[edytuj | edytuj kod]
Problemy z zakresu kombinatoryki[edytuj | edytuj kod]
Problemy związane z ciągami i szeregowaniem[edytuj | edytuj kod]
Inne problemy[edytuj | edytuj kod]
Przypisy[edytuj | edytuj kod]
- ↑ R.W. Kaye, Minesweeper and NP-completeness. [dostęp 2007-07-16]. [zarchiwizowane z tego adresu (2006-12-16)].
- ↑ Demaine, Hohenberger, Liben-Nowell, Tetris is Hard, Even to Approximate