결정 문제

계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다. 일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합의 유한한 부분집합이기 때문에, 모든 문제는 결정 문제로 환원될 수 있다.

판정 문제를 푸는 데 쓰인 방법을 알고리즘이라고 한다. 어떤 판정 문제를 푸는 알고리즘이 있으면 그 문제는 결정 가능하다고 한다. 없으면 결정 불가능하다고 한다.

같이 보기

• 정지 문제
• 결정가능성