계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 입력에 대해 '예' 또는 '아니오'로 답할 수 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 또는 "주어진 자연수가 소수인가?"와 같은 질문이 이에 해당한다. 답은 입력 값에 따라 '예' 또는 '아니오' 중 하나로 결정된다.
결정 문제를 푸는 데 사용되는 방법을 알고리즘이라고 한다. 어떤 결정 문제를 푸는 알고리즘이 존재하면 그 문제는 결정 가능(decidable)하다고 하며, 존재하지 않으면 결정 불가능(undecidable)하다고 한다.
결정 문제의 개념은 1928년 다비트 힐베르트(David Hilbert)와 빌헬름 아커만(Wilhelm Ackermann)이 제기한 엔트셰이둥스프로블렘(Entscheidungsproblem, 독일어로 '결정 문제')에서 비롯되었다. 이는 주어진 1차 논리 명제가 보편적으로 타당한지(즉, 모든 구조에서 참인지)를 판별하는 알고리즘의 존재를 묻는 문제였다. 1936년 알론조 처치(Alonzo Church)와 앨런 튜링(Alan Turing)은 각각 독립적으로 이러한 일반적인 알고리즘은 존재할 수 없음을 증명하였다. 튜링은 이 문제를 정지 문제(halting problem)로 환원하여 증명하였으며, 이는 계산 가능성 이론의 핵심 결과로 자리 잡았다.
계산 복잡도 이론에서는 결정 가능한 결정 문제들을 해결에 필요한 계산 자원(시간, 공간)의 양에 따라 분류한다. 대표적인 복잡도 종류로는 P(다항 시간 내에 결정론적으로 해결 가능한 문제), NP(다항 시간 내에 비결정론적으로 해결 가능한 문제) 등이 있다. NP-완전 문제는 NP에 속하면서도 다른 모든 NP 문제를 다항 시간 안에 환원할 수 있는 문제로, P-NP 문제는 이 두 복잡도 종류가 동일한지에 대한 미해결 난제이다.
결정 문제는 최적화 문제(optimization problem)와 밀접하게 관련되어 있다. 최적화 문제는 주어진 조건에서 목표 함수의 값을 최대화하거나 최소화하는 해를 찾는 문제인 반면, 결정 문제는 '예/아니오'로 답하는 문제이다. 일반적으로 최적화 문제는 대응하는 결정 문제를 반복적으로 해결함으로써 풀 수 있다.
결정 문제의 대표적인 예로는 소수 판정 문제(주어진 수가 소수인가?), SAT 문제(주어진 부울 논리식을 만족하는 변수 값이 존재하는가?), 그래프 연결성 문제(주어진 그래프가 연결되어 있는가?), 해밀턴 경로 문제(주어진 그래프에 모든 정점을 정확히 한 번씩 방문하는 경로가 존재하는가?) 등이 있다.
