정의
판별 문제(Decision Problem)란, 주어진 입력에 대해 “예(Yes)” 또는 “아니오(No)”의 두 가지 답변 중 하나로 결과를 판단하도록 요구되는 문제를 의미한다. 입력이 특정 조건을 만족하는지 여부를 판단하는 형태이므로, 답이 이진(yes·no) 형태로 제한된다.
학문적 맥락
| 분야 | 활용 예시 |
|---|---|
| 이론 컴퓨터 과학 | 결정론적·비결정론적 튜링 기계 모델에서 정의되는 문제. 대표적으로 SAT(만족도 문제), 정점 커버 판별 문제, 그래프 이분성 판별 문제 등이 있다. |
| 수학 | 정리나 명제의 진위 여부를 판단하는 문제. 예를 들어, 주어진 다항식이 특정 범위 내에서 양수인지 여부를 판단하는 문제 등이 있다. |
| 인공지능·기계학습 | 분류(classification) 문제와 유사하게, 입력 데이터를 사전에 정의된 카테고리 중 하나에 할당하는 작업을 가리키는 경우가 있다. 다만, 기계학습에서는 보통 확률적 출력이 포함되므로 엄밀히 말하면 판별 문제와는 구분된다. |
| 논리학 | 형식 논리식이 참인지 거짓인지 판단하는 타당성 검증 문제 등이 포함된다. |
특징
- 이진 응답: 답이 “예” 혹은 “아니오”로 명확히 구분된다.
- 복잡도 이론에서의 중요성: 판별 문제의 시간·공간 복잡도를 분석함으로써 P, NP, NP‑complete, NP‑hard 등 복잡도 클래스가 정의된다.
- 환원(reduction) 활용: 복잡도 이론에서 한 판별 문제를 다른 판별 문제로 환원함으로써 문제의 난이도를 비교한다.
대표적인 판별 문제
- SAT (Boolean Satisfiability Problem): 주어진 부울식이 참이 되게 할당이 존재하는가?
- HALTING PROBLEM: 임의의 튜링 기계와 입력에 대해 기계가 멈출(정지할)지 여부를 결정할 수 있는가? (이 문제는 결정 불가능한 판별 문제에 속한다.)
- 그래프 컬러링 판별 문제: 주어진 그래프가 k-색으로 색칠될 수 있는가?
응용
- 알고리즘 설계: 판별 문제를 해결하기 위한 알고리즘은 최적화 문제나 검색 문제의 기본이 된다.
- 보안: 암호학에서 난이도 기반 보안 프로토콜은 특정 판별 문제(예: 소인수분해)의 어려움에 의존한다.
- 자동화 검증: 소프트웨어·하드웨어 검증 과정에서 시스템이 특정 사양을 만족하는지 판별하는 데 활용된다.
관련 용어
- 결정 문제: 판별 문제와 동의어로 사용된다.
- 결정 가능성(Decidability): 모든 입력에 대해 알고리즘적으로 ‘예’ 혹은 ‘아니오’를 판별할 수 있는 여부.
- 복잡도 클래스: P, NP, co‑NP 등 판별 문제의 계산 난이도를 분류하는 체계.
