결정 문제

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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