결정 문제

모든 입력에 대해 「예」 또는 「아니오」 가운데 하나로 답하는 문제다. 「이 수는 소수인가」, 「이 지도를 세 가지 색으로 칠할 수 있는가」가 그 예다. P·NP 같은 복잡도 종류는 결정 문제의 모임으로 정의한다. 가장 좋은 값을 구하는 최적화 문제도 「값이 k 이하인 해가 있는가」 꼴로 바꾸면 결정 문제가 된다. 형식적으로는 답이 「예」인 입력 문자열들의 집합, 곧 언어(language)로 다룬다.