Lista problemów NP-zupełnych

Spis treści

Logika

• Problem spełnialności (SAT)

Problemy grafowe

• 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

Problemy podziału zbioru

• Problem plecakowy
• Problem trójpodziału
• Problem podziału
• Problem podzbioru o zadanej sumie

Problemy z zakresu kombinatoryki

• Programowanie zero-jedynkowe

Problemy związane z ciągami i szeregowaniem

• Optymalne szeregowanie zadań dla wielu procesorów

Inne problemy

• Saper (gra komputerowa)
• Tetris (gra komputerowa)