결정 문제: 두 판 사이의 차이

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