La questione se una macchina di Turing possa dimostrare che le classi NP (tempo polinomiale non deterministico) e P (tempo polinomiale) sono le stesse è uno dei problemi aperti più profondi e di lunga data nella teoria della complessità computazionale. Per affrontare questa domanda in modo esaustivo, è essenziale considerare le definizioni e le caratteristiche delle macchine di Turing