تالار گفتمان مانشت

While algorithms are polynomially reducible to deterministic Turing machines,
->=
it is not known whether nondeterministic Turing machines are polynomially reducible to deterministic Turing machines.
->=
Thus, it is not known whether P = NP

(although P is contained in NP, P ⊆ NP, since any deterministic Turing machine can

be viewed as a nondeterministic one). However, in practical terms, if we want to simulate a nondeterministic Turing machine using a deterministic one, the complexity increases exponentially.