Ein Problem gehört zur Klasse NP (nichtdeterministisch polynomiell), wenn es in polynomieller Zeit von einer nichtdeterministischen Turingmaschine gelöst werden kann. Das bedeutet, dass eine Lösung in einer angemessenen Zeit verifiziert, aber möglicherweise nicht effizient gefunden werden kann. NP-Probleme sind Entscheidungsprobleme, bei denen Ja- oder Nein-Antworten erwartet werden.