Tuttavia, alcuni problemi computazionali sono più facili da analizzare in termini di risorse più insolite. Ad esempio, una macchina Turing non deterministica è un modello computazionale che permette di diramare per verificare contemporaneamente molte possibilità diverse. La macchina non-deterministica Turing ha molto poco a che fare con come fisicamente vogliamo calcolare algoritmi, ma la sua ramificazione cattura esattamente molti dei modelli matematici che vogliamo analizzare, in modo che il tempo non-deterministico è una risorsa molto importante nell' analisi dei problemi computazionali.
Che tipo di macchina Turing può essere caratterizzata verificando contemporaneamente più possibilità?
non-deterministic non-deterministic