Supóngase que un problema perteneciente a NP es resuelto por una máquina de Turing "M" = ("Q", "Σ", "i", "F", "δ") (donde "Q" es el conjunto de estados, "Σ" es el alfabeto de símbolos de la cinta, "i" ∈ "Q" es el estado inicial, "F" ⊆ "Q" es el conjunto de estados de aceptación y "δ" ⊆ "Q" × "Σ" × "Q" × "Σ" × {−1,+1} el conjunto de transiciones) y que "M" acepta o rechaza una instancia del problema en tiempo "p"("n") donde "n" es el tamaño de la instancia y "p" es una función polinómica.