Eine Sprache gehört zu NP, wenn sie von einer nichtdeterministischen Turingmaschine in Polynomzeit entschieden wird.

Eine Sprache gehört zu NP, wenn sie von einer Turningmaschine mit polynomieller Platzkomplexität entschieden wird.

Eine Sprache gehört zu NP, wenn sie nicht von einer Turingmaschine in Polynomzeit entschieden werden kann.