Dany problem może zostać rozwiązany w czasie wielomianowym na niedeterministycznej maszynie Turinga wtedy i tylko wtedy, gdy poprawność rozwiązania tego problemu jest weryfikowalna w czasie wielomianowym na deterministycznej maszynie Turinga. Tego rodzaju problemy należą do klasy NP (nondeterministic polynomial time).
Definicja formalna Niedeterministyczna maszyna Turinga to krotka:
gdzie: – zbiór stanów maszyny – alfabet taśmy z wyróżnionym symbolem zerowym – stan początkowy – zbiór stanów końcowych – podzbiór iloczynu kartezjańskiego
Jedyna istotna różnica względem definicji deterministycznej maszyny Turinga polega na zastąpieniu funkcji postaci
relacją
Z tego powodu deterministyczne maszyny Turinga można traktować jako szczególne przypadki niedeterministycznych maszyn Turinga, mianowicie takich w których jest funkcją.
Obliczeniowa równoważność z deterministyczną maszyną Turinga Niedeterministyczne maszyny Turinga podlegają dokładnie takim samym ograniczeniom obliczeniowym (patrz: problem stopu) jakim podlegają deterministyczne maszyny Turinga.