결정 불가능

모든 입력에 대해 유한한 시간 안에 옳은 답을 내는 알고리즘이 아예 존재하지 않는 결정 문제를 결정 불가능하다고 한다. 정지 문제가 대표적이고, 정수 계수 다항 방정식에 정수해가 있는지 판정하는 문제(힐베르트의 열째 문제)도 그렇다. 「오래 걸린다」와는 전혀 다른 말이다. P, NP, EXP 의 문제는 모두 결정 가능하며, P 대 NP 는 결정 가능한 문제들 안에서 「현실적인 시간에 풀리는가」를 가르는 질문이다. P 대 NP 라는 명제 자체가 표준 공리계에서 증명도 반증도 안 될 수 있다는 이야기는 이와 구별해야 한다.