의사결정 문제
Decision problem
계산 가능성 이론과 계산 복잡도 이론에서 의사결정 문제는 입력 값에 대한 예/아니오 질문으로 제기될 수 있는 문제입니다.결정 문제의 예로는 주어진 자연수가 소수인지 여부를 결정하는 것입니다.또 다른 문제는 "x와 y의 두 숫자가 주어졌을 때 x가 y를 균등하게 나눕니까?"입니다.답은 x와 y의 값에 따라 '예' 또는 '아니오'입니다.알고리즘의 형태로 주어진 결정 문제를 해결하는 방법을 해당 문제에 대한 결정 절차라고 합니다."두 개의 숫자 x와 y가 주어졌을 때, x가 y를 균등하게 나누나요?"라는 결정 문제에 대한 결정 절차는 x가 y를 균등하게 나누는지 여부를 결정하기 위한 단계를 제공합니다.그러한 알고리즘 중 하나가 롱 나눗셈입니다.나머지가 0이면 답은 '예'이고, 그렇지 않으면 '아니오'입니다.알고리즘으로 해결할 수 있는 결정 문제를 결정 가능이라고 합니다.
결정문제는 일반적으로 결정가능성의 수학적 질문, 즉, 집합에서 어떤 물체의 존재 또는 구성원을 결정하는 효과적인 방법의 존재에 대한 질문에서 나타난다; 수학에서 가장 중요한 문제들 중 일부는 결정할 수 없다.
계산 복잡도 분야는 해결의 난이도에 따라 결정 가능한 의사결정 문제를 분류합니다.이러한 의미에서 "어렵다"는 특정 문제에 대해 가장 효율적인 알고리즘이 필요로 하는 계산 자원의 관점에서 설명됩니다.한편, 재귀 이론의 분야는 결정 불가능한 결정 문제를 튜링 정도에 따라 분류하는데, 이것은 어떤 해결책에 내재된 계산 불가능성의 척도이다.
정의.
결정 문제는 무한 입력 세트에 대한 예스 또는 노 질문입니다.의사결정 문제를 답이 [1]예인 입력 집합과 함께 가능한 입력 집합으로 정의하는 것이 전통이다.
이러한 입력은 자연수일 수 있지만 이진 문자열이나 다른 알파벳 위의 문자열과 같은 다른 종류의 값일 수도 있습니다.문제가 "yes"를 반환하는 문자열의 서브셋은 형식 언어이며, 의사결정 문제는 형식 언어로 정의되는 경우가 많습니다.
Gödel 번호부여 등의 부호화를 사용하면 임의의 문자열을 자연수로 부호화할 수 있으며 이를 통해 결정 문제를 자연수의 서브셋으로 정의할 수 있습니다.따라서 결정 문제의 알고리즘은 자연수의 부분 집합의 특성 함수를 계산하는 것입니다.
예
결정 가능한 결정 문제의 전형적인 예는 소수 집합이다.중요하지 않은 모든 요인을 시험함으로써 주어진 자연수가 소수인지 아닌지를 효과적으로 결정할 수 있다.훨씬 더 효율적인 원시성 테스트 방법이 알려져 있지만, 효과적인 방법의 존재만으로도 결정성을 확립하기에 충분하다.
결정 가능성
결정 문제는 답이 예인 입력(또는 자연수) 집합이 재귀 집합인 경우 결정 가능하거나 효과적으로 해결할 수 있습니다.답이 yes인 입력(또는 자연수) 집합이 재귀적으로 열거할 수 있는 집합인 경우 문제는 부분적으로 결정 가능, 반감 가능, 해결 가능 또는 입증 가능입니다.결정할 수 없는 문제는 결정할 수 없다.이러한 경우 효율적인 알고리즘이든 그렇지 않은 알고리즘이든 해결할 수 없습니다.
정지 문제는 결정 불가능한 중요한 문제이며, 더 많은 예에 대해서는 결정 불가능한 문제의 목록을 참조하십시오.
완전한 문제
의사결정 문제는 다원적 감소성에 따라 정렬할 수 있으며 다항식 시간 감소와 같은 실현 가능한 감소와 관련된다.판정문제 P는 P가 S의 멤버이며, S의 모든 문제를 P로 저감할 수 있는 경우에는 판정문제 S의 집합 S에 대해 완료라고 한다.완전한 의사결정 문제는 의사결정 문제의 복잡성 클래스를 특징짓기 위해 계산 복잡성 이론에서 사용된다.예를 들어, 부울 만족도 문제는 다항식 시간 감소성 하에서 결정 문제의 클래스 NP에 대해 완전하다.
기능상의 문제
의사결정 문제는 단순한 '예' 또는 '아니오'보다 더 복잡한 답을 가진 기능 문제와 밀접하게 관련되어 있습니다.대응하는 함수 문제는 "2개의 숫자 x와 y가 주어지면 x를 y로 나눈 것은 무엇인가?"입니다.
함수 문제는 부분 함수 f로 구성됩니다. 비공식적인 "문제"는 함수 f가 정의된 입력에 대한 f의 값을 계산하는 것입니다.
모든 함수 문제는 결정 문제로 바뀔 수 있습니다. 결정 문제는 관련 함수의 그래프에 불과합니다.(함수 f의 그래프는 f(x) = y가 되는 쌍(x,y)의 집합이다.)이 결정 문제가 효과적으로 해결된다면 함수 문제도 해결될 것입니다.그러나 이러한 감소는 계산의 복잡성을 고려하지 않는다.예를 들어 함수의 그래프는 다항시간(이 경우 실행시간은 쌍(x,y)의 함수로서 계산된다)으로 결정될 수 있다(이 경우 실행시간은 x만의 함수로서 계산된다).함수 f(x) = 2에는x 이 특성이 있습니다.
모든 결정문제는 결정문제와 관련된 집합의 특성함수를 계산하는 함수문제로 변환할 수 있다.이 함수가 계산 가능한 경우 관련 결정 문제를 결정할 수 있습니다.그러나, 이러한 감소는 계산 복잡도에 사용되는 표준 감소보다 더 자유롭다. 예를 들어, NP-완전 문제와 그 co-NP-완전 보의 특성 함수의 복잡성은 기본적인 의사결정 문제가 그렇지 않더라도 정확히 동일하다.일부 전형적인 계산 모델에서 동등하다고 간주됩니다.
최적화 문제
각 입력에 대해 정답이 하나만 있는 의사결정 문제와 달리, 최적화 문제는 특정 입력에 대한 최적의 답을 찾는 것과 관련이 있습니다.최적화 문제는 출장 세일즈맨 문제나 선형 프로그래밍에 관한 많은 질문 등 많은 애플리케이션에서 자연스럽게 발생합니다.
기능 및 최적화 문제를 의사결정 문제로 변환하기 위한 표준 기술이 있습니다.예를 들어, 여행 세일즈맨 문제에서 최적화 문제는 최소 무게로 투어를 제작하는 것입니다.관련된 결정 문제는 각 N에 대해 그래프에 가중치가 N보다 작은 투어가 있는지 확인하는 것입니다.결정 문제에 반복적으로 답변함으로써 투어의 최소 가중치를 찾을 수 있습니다.
의사결정 문제의 이론이 매우 잘 개발되었기 때문에, 복잡성 이론의 연구는 전형적으로 의사결정 문제에 초점을 맞추었다.최적화 문제 자체는 여전히 연산성 이론과 운영 연구 등의 분야에서 관심을 끌고 있습니다.
「 」를 참조해 주세요.
레퍼런스
- Kozen, D.C. (2012). Automata and Computability. Springer. ISBN 9781461218449.
- Hartley, Rogers, Jr (1987). The Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 9780262680523.
- Sipser, M. (2020). Introduction to the Theory of Computation. Cengage Learning. ISBN 9780357670583.
- Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer. ISBN 0-387-15299-7.
- Kroening, Daniel; Strichman, Ofer (23 May 2008). Decision procedures. Springer. ISBN 978-3-540-74104-6.
- Bradley, Aaron; Manna, Zohar (3 September 2007). The calculus of computation. Springer. ISBN 978-3-540-74112-1.
