비결정적 튜링 기계

각 단계에서 다음 동작이 하나로 정해지지 않고 여러 가지 가운데 고를 수 있는 튜링 기계다(비결정론적 튜링 기계라고도 한다). 가능한 계산 경로 가운데 하나라도 받아들이면 답을 「예」로 본다. 실제로 만들 수 있는 기계가 아니라 정의를 위한 도구이며, 「정답을 운 좋게 찍은 뒤 확인만 하는 기계」로 이해하면 된다. NP 는 이 기계가 다항 시간에 푸는 결정 문제의 모임이고, 이는 검증자를 쓴 정의와 같다. 보통의(결정적) 튜링 기계로 흉내 낼 수는 있지만 알려진 방법은 지수 시간이 든다.