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 Problem zbioru niezależnego
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)Demaine, Hohenberger, Liben-Nowell, Tetris is Hard, Even to Approximate
Przypisy
Kategoria:Teoria obliczeń P