결정 문제
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
결정 문제는 무한 집합의 입력에 대해 예/아니오로 답하는 질문이다. 입력은 자연수, 이진 문자열 등 다양한 형태일 수 있으며, 문제에서 '예'를 반환하는 입력의 집합은 형식 언어로 정의되기도 한다. 결정 문제는 결정 가능성 여부에 따라 분류되며, 정지 문제와 같은 결정 불가능한 문제도 존재한다. 결정 문제는 다대일 환원 가능성에 따라 완전 문제로 정렬될 수 있으며, 계산 복잡도 이론에서 복잡도 종류를 특징짓는 데 사용된다. 또한, 결정 문제는 함수 문제 및 최적화 문제와 밀접한 관련이 있으며, 계산 복잡성 연구에 중요한 역할을 한다.
더 읽어볼만한 페이지
- 계산 문제 - 다체 문제
다체 문제는 상호작용하는 여러 물체의 운동을 다루는 문제로, 특히 중력적으로 상호작용하는 천체들의 운동을 예측하는 문제가 대표적이며, 삼체 문제부터는 해석적 해를 구하기 어려워 섭동 이론이나 수치 해석 등의 방법이 활용된다. - 계산 문제 - 최적화 문제
최적화 문제는 주어진 제약 조건 하에 특정 목적 함수의 값을 최소화하거나 최대화하는 해를 찾는 문제로, 제약 조건 유무, 함수 종류, 변수 성격에 따라 다양한 유형으로 나뉜다. - 계산 가능성 이론 - 처치-튜링 논제
처치-튜링 논제는 모든 효과적인 계산 과정이 튜링 기계로 수행될 수 있다는 가설로, 알고리즘과 계산 가능성의 본질에 대한 논의를 촉발하며 컴퓨터 과학과 철학 분야에서 활발히 연구되고 있다. - 계산 가능성 이론 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
| 결정 문제 | |
|---|---|
| 개요 | |
| 분야 | 계산 가능성 이론, 계산 복잡도 이론 |
| 성격 | 예-아니오 문제 |
| 관련 주제 | 함수 문제, 검색 문제, 최적화 문제 |
| 정의 | |
| 설명 | 어떤 입력이 주어졌을 때 그에 대한 답이 '예' 또는 '아니오'로 나오는 문제를 말한다. 이는 튜링 기계와 같은 추상적인 계산 모델에서 연구되며, 문제의 해결 가능성 및 효율성을 분석하는 데 중요한 역할을 한다. |
| 특징 | |
| 형식 언어와의 관계 | 형식 언어 L에 대해, 문자열 w가 L에 속하는지 여부를 묻는 문제는 결정 문제로 볼 수 있다. |
| 튜링 기계와의 관계 | 결정 문제는 튜링 기계로 해결할 수 있는지, 그리고 얼마나 효율적으로 해결할 수 있는지를 평가하는 데 사용된다. |
| 예시 | |
| 예시 | 주어진 수가 짝수인가? 주어진 그래프가 연결 그래프인가? "주어진 부울 식이 참이 되는 변수 할당이 존재하는가?" (SAT) |
| 복잡도 종류 | |
| 설명 | 결정 문제의 복잡도는 문제를 해결하는 데 필요한 계산 자원(시간, 공간 등)에 따라 정의된다. |
| 주요 복잡도 종류 | P: 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제들의 집합 NP: 비결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 문제들의 집합 NP-완전: NP에 속하며, NP에 속하는 모든 문제를 다항 시간 안에 변환할 수 있는 문제들의 집합 NP-난해: NP에 속하는 모든 문제를 다항 시간 안에 변환할 수 있는 문제들의 집합 (반드시 NP에 속할 필요는 없음) |
| 중요성 | |
| 설명 | 결정 문제는 이론 컴퓨터 과학의 핵심적인 개념으로, 문제의 계산 복잡성을 이해하고 효율적인 알고리즘을 설계하는 데 중요한 역할을 한다. 또한, 암호학, 인공지능 등 다양한 분야에 응용된다. |
| 관련 개념 | |
| 관련 개념 | 알고리즘, 튜링 기계, 계산 복잡도 이론, NP-완전 문제 |
2. 정의
결정 문제는 무한 집합의 입력에 대해 '예' 또는 '아니오'라는 답을 요구하는 질문이다. 일반적으로 결정 문제는 가능한 모든 입력의 집합과 그중에서 답이 '예'가 되는 입력들의 집합으로 정의된다.[1]
결정 가능한 결정 문제의 대표적인 예시로 소수의 집합을 들 수 있다. 어떤 자연수가 주어졌을 때, 이 수가 소수인지 아닌지는 가능한 모든 약수를 직접 나누어보는 방식으로 효과적으로 알아낼 수 있다. 물론 이보다 훨씬 효율적인 소수 판별법들이 알려져 있지만, 이렇게 효과적으로 답을 찾을 수 있는 방법이 존재한다는 사실 자체만으로도 이 문제가 결정 가능하다는 것을 보여준다.
어떤 결정 문제에서 답이 "예"가 되는 입력들의 집합이 재귀 집합일 경우, 그 문제는 결정 가능(decidable)하거나 효과적으로 해결 가능(effectively solvable)하다고 말한다. 만약 답이 "예"인 입력들의 집합이 재귀적 가산 집합이라면, 그 문제는 부분 결정 가능(partially decidable), 반 결정 가능(semidecidable), 해결 가능(solvable), 또는 증명 가능(provable)하다고 한다.
결정 문제는 다대일 환원 가능성에 따라 정렬될 수 있으며, 다항 시간 환원과 같은 실행 가능한 환원과 관련이 있다. 어떤 결정 문제 ''P''가 결정 문제 집합 ''S''의 구성원이고, ''S''에 속하는 모든 문제가 ''P''로 환원될 수 있다면, ''P''는 집합 ''S''에 대해 ''완전''하다고 말한다. 완전 결정 문제는 계산 복잡도 이론에서 결정 문제의 복잡도 종류를 특징짓는 데 중요한 역할을 한다. 예를 들어, 부울 만족 가능성 문제는 다항 시간 환원 하에서 결정 문제의 종류 NP에 대해 완전한 대표적인 문제이다.
결정 문제는 '예' 또는 '아니오'보다 더 복잡한 답을 요구하는 함수 문제와 밀접하게 연관되어 있다. 예를 들어, "두 숫자 x와 y가 주어졌을 때, x를 y로 나눈 값은 무엇인가?"와 같은 문제가 함수 문제에 해당한다.
결정 문제는 각 입력에 대해 예/아니오 중 하나의 답만 가지는 반면, 최적화 문제는 특정 입력에 대해 "가장 좋은" 답을 찾는 문제이다. 외판원 문제나 선형 계획법과 관련된 많은 문제들이 최적화 문제에 해당한다.
결정 문제의 입력은 자연수일 수도 있고, 이진 문자열이나 특정 알파벳으로 이루어진 문자열 등 다양한 형태가 될 수 있다. 문제에 대해 '예'라는 답을 주는 문자열들의 부분 집합은 형식 언어로 볼 수 있으며, 따라서 결정 문제는 종종 형식 언어로 정의되기도 한다.
괴델 수와 같은 특별한 방법을 사용하면, 모든 문자열을 자연수로 바꾸어 표현(인코딩)할 수 있다. 이를 통해 어떤 결정 문제든 자연수의 부분 집합 문제로 바꾸어 정의할 수 있게 된다. 결국, 결정 문제를 푸는 알고리즘은 특정 자연수 부분 집합에 어떤 수가 속하는지 아닌지를 판별하는 특성 함수를 계산하는 것과 같다.
3. 예시
4. 결정 가능성
결정 불가능(undecidable)한 문제도 존재한다. 이런 문제들은 결정 가능하지 않으며, 문제를 풀 수 있는 효율적인 알고리즘뿐만 아니라 어떤 종류의 알고리즘도 존재하지 않는다.
대표적인 결정 불가능 문제로는 정지 문제가 있다. 더 많은 예시는 결정 불가능 문제 목록에서 찾아볼 수 있다.
5. 완전 문제
6. 함수 문제와의 관계
함수 문제는 어떤 부분 함수 f에 대해, 주어진 입력 값에 대한 f의 값을 계산하는 문제이다.
모든 함수 문제는 그 함수의 그래프를 이용해 결정 문제로 변환될 수 있다. 함수의 그래프란 f(x) = y를 만족하는 모든 입력과 출력의 쌍 (x, y)의 집합을 의미한다. 따라서 함수 문제를 "주어진 쌍 (x, y)가 함수 f의 그래프에 속하는가?"라는 결정 문제로 바꿀 수 있다. 만약 이 결정 문제를 효율적으로 풀 수 있다면, 원래의 함수 문제도 풀 수 있는 것처럼 보일 수 있다.
하지만 이러한 변환은 계산 복잡성을 그대로 보존하지는 않는다. 예를 들어, 어떤 함수의 그래프에 속하는지 판별하는 것은 다항 시간 안에 가능하더라도(이때 실행 시간은 입력 쌍 (x, y)의 크기에 따라 결정됨), 함수 값 자체를 계산하는 것은 다항 시간 안에 불가능할 수 있다(이때 실행 시간은 입력 x만의 크기에 따라 결정됨). 함수 f(x) = 2x가 대표적인 예시이다. 이 함수의 그래프, 즉 (x, 2x) 형태의 쌍인지 확인하는 것은 상대적으로 빠를 수 있지만, x가 주어졌을 때 2x 값을 직접 계산하는 것은 x가 커짐에 따라 급격히 어려워진다.
반대로, 모든 결정 문제는 관련된 집합의 특성 함수를 계산하는 함수 문제로 변환될 수 있다. 특성 함수는 어떤 원소가 집합에 속하면 1을, 속하지 않으면 0을 반환하는 함수이다. 이 특성 함수를 계산할 수 있다면, 원래의 결정 문제도 해결할 수 있다. 그러나 이 변환 방식은 계산 복잡도 이론에서 일반적으로 사용하는 다항 시간 변환과는 다소 차이가 있다. 예를 들어, NP-완전 문제와 그 보완 문제(co-NP-완전)는 현재까지는 다항 시간 내에 서로 변환될 수 있다고 여겨지지 않지만, 각각의 특성 함수를 계산하는 문제의 복잡성은 동일하다.
7. 최적화 문제와의 관계
함수 문제나 최적화 문제는 종종 결정 문제로 변환하여 다루어진다. 이는 특정 값과 출력이 특정 관계(예: "같다", "작거나 같다")를 만족하는지 묻는 방식으로 이루어진다. 이렇게 변환하면 해당 결정 문제의 복잡성을 연구할 수 있고, 많은 경우 이 결정 문제를 해결함으로써 원래의 함수 문제나 최적화 문제를 풀 수 있다. 예를 들어, 외판원 문제에서 최적화 문제는 가장 작은 가중치를 가지는 경로를 찾는 것이다. 이와 관련된 결정 문제는 "주어진 값 N에 대해, 그래프에 가중치의 합이 N보다 작은 경로가 존재하는가?"이다. 이 결정 문제에 반복적으로 답함으로써 경로의 최소 가중치를 찾아낼 수 있다.
결정 문제에 대한 이론이 잘 발달했기 때문에, 계산 복잡성 이론 연구는 주로 결정 문제에 초점을 맞추어 왔다. 하지만 최적화 문제 자체도 운영 과학이나 계산 가능성 이론과 같은 분야에서 중요한 연구 대상이다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com