Kompleksitet klassen beslutning problemer som svar kan kontrolleres av en algoritme som operasjonstiden er polynom i størrelsen på inndataene. Merk at dette ikke krever eller innebærer at svar kan finnes raskt, bare at noen hevdet løsning kan verifiseres raskt. "NP" er klassen som en deterministiske Turing machine godtar i Polynomisk tid.