정의
결정 문제(Decision Problem)는 주어진 입력에 대해 '예' 또는 '아니오'의 두 가지 가능한 출력 중 하나를 산출하도록 요구하는 문제 유형이다. 계산 이론과 수리 논리학에서 결정 문제는 알고리즘으로 해결 가능한지를 판단하는 데 중심적인 역할을 한다.
개요
결정 문제는 이론 컴퓨터 과학, 특히 계산 가능성 이론과 계산 복잡도 이론에서 중요한 개념이다. 문제의 형태는 일반적으로 "주어진 문자열이 특정 언어에 속하는가?"와 같은 질문으로 표현된다. 예를 들어, 자연수 n이 소수인지 여부를 판단하는 문제는 결정 문제에 해당하며, 입력이 소수이면 '예', 그렇지 않으면 '아니오'를 출력한다. 결정 문제는 결정 가능(Recursively Decidable)인지, 혹은 결정 불가능(Undecidable)인지에 따라 분류된다. 유명한 예로는 정지 문제(Halting Problem)가 있으며, 이는 튜링 기계가 주어진 입력에서 유한 시간 안에 정지할지를 판단하는 문제로, 결정 불가능한 문제의 전형적인 사례이다.
어원/유래
"결정 문제"는 영어 "decision problem"의 번역어로, 원래는 독일어로 "Entscheidungsproblem"이라는 용어로 수학 기초론에서 처음 사용되었다. 이 용어는 20세기 초 수학자 다비트 힐베르트(David Hilbert)가 제시한 수학의 기본 문제 중 하나로, 모든 수학적 명제에 대해 알고리즘적으로 참 또는 거짓을 결정할 수 있는 방식이 존재하는지 묻는 것이었다. 이후 앨런 튜링과 알론조 처치는 이 문제에 대한 부정적인 해답을 제시하면서 결정 불가능한 문제가 존재함을 보임으로써 계산 이론의 기초를 마련했다.
특징
결정 문제의 주요 특징은 해답이 이산적인 두 값('예' 또는 '아니오')으로 제한된다는 점이다. 이는 최적화 문제(Optimization Problem)나 함수 문제(Function Problem)와 구별되는 점이다. 또한, 대부분의 알고리즘 문제는 결정 문제 형태로 변환할 수 있으며, 복잡도 이론에서는 결정 문제를 기반으로 P, NP, NP-완전 등 복잡도 클래스를 정의한다. 결정 문제는 문제의 난이도를 상대적으로 분석하는 데 유용한 도구로 활용된다.
관련 항목
- 정지 문제 (Halting Problem)
- 튜링 기계 (Turing Machine)
- 계산 가능성 이론 (Computability Theory)
- 계산 복잡도 이론 (Computational Complexity Theory)
- P와 NP 문제 (P vs NP Problem)
- 엔치다이운스프로블럼 (Entscheidungsproblem)