2.6. Nevezetes NP bonyolultságú problémák

3 színnel színezhető gráfok: Adott egy gráf, s döntsük el, hogy kiszínezhet ők-e a gráf csúcsai úgy, hogy két szomszédos (éllel összekötött) csúcs se legyen azonos színű. A megfelelő tanú maga a színezés.

Hamilton-kör: Adott egy gráf, s mondjuk meg, hogy létezik-e benne olyan kör, mely minden csúcsot pontosan egyszer tartalmaz. A tanú maga a Hamilton-kör.

SAT: Kielégíthető-e egy Boole-formula? A tanú maga az értékelés.

A kutatások során az derült ki, hogy az előbb felsorolt feladatok egyformán nehéz problémák. Sokan sejtik, de bizonyítani még nem sikerült, hogy P≠NP.