계산 문제

Computational problem

이론 컴퓨터 과학에서 계산 문제는 컴퓨터가 해결할 수 있는 문제 또는 컴퓨터가 대답할 수 있는 문제다. 예를 들어, 팩토링의 문제는

"양수 n을 주어진다면 n의 비경쟁적 주요 인자를 찾아라."

계산상의 문제야 계산적 문제는 모든 인스턴스/사례에 대해 빈 솔루션 집합과 함께 인스턴스 또는 사례 집합으로 볼 수 있다. 예를 들어, 인수 문제에서 예는 정수 n이고 해결책은 n의 비독점적 주요 요소를 설명하는 소수 p이다.

컴퓨터 문제는 이론 컴퓨터 과학에서 주요 연구 대상 중 하나이다. 계산 복잡성 이론의 분야는 주어진 문제를 해결하기 위한 자원의 양(컴퓨팅 복잡성)을 결정하고, 왜 어떤 문제들이 난해하거나 이해할 수 없는 것인지 설명할 필요가 있을 것이다. 계산 문제는 다양한 추상적인 기계로 그것들을 계산(솔브)하는 데 걸리는 자원(예: 시간, 공간/메모리, 에너지, 회로 깊이)을 폭넓게 정의하는 복잡성 등급에 속한다. 예를 들어, 캐시컬 시스템의 경우 복잡도 클래스 P, 양자 시스템의 경우 BQP.

인스턴스(instance)와 솔루션(solution)을 모두 이진 문자열(즉, {0,*[a] 1)로 나타내는 것은 많은 문제의 전형적이다. 예를 들어, 이진 인코딩을 사용하여 숫자를 이진 문자열로 나타낼 수 있다.

종류들

의사결정 문제

의사결정 문제는 모든 경우에 대한 답이 예스 또는 아니오인 계산적 문제다. 의사결정 문제의 예는 원시성 시험이다.

"양수 정수 n을 지정하면 n이 prime인지 판단한다."

의사결정 문제는 일반적으로 답이 "예"인 모든 경우의 집합으로 표현된다. 예를 들어, 원시성 시험은 무한 집합으로 나타낼 수 있다.

L = {2, 3, 5, 7, 11, ...}

검색문제

검색 문제에서 답은 임의의 문자열일 수 있다. 예를 들어, 인수인계는 인스턴스(instance)가 양의 정수이고 해결책은 소수 집합인 검색 문제다.

검색 문제는 검색 관계라고 하는 모든 인스턴스-솔루션 쌍으로 구성된 관계로 표현된다. 예를 들어, 인소싱은 관계로 나타낼 수 있다.

R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}

이는 모든 한 쌍의 숫자(n, p)로 구성되며, 여기서 p는 n의 비독점적 주요 요인이다.

카운팅 문제

계산 문제는 주어진 검색 문제에 대한 해결책의 수를 요구한다. 예를 들어, 인수와 관련된 계산 문제는

"n의 양의 정수 n을 지정하면 n의 비경쟁적 주요 인자의 수를 세십시오."

계수 문제는 {0, 1}*부터 비음수 정수까지의 함수 f로 나타낼 수 있다. 검색 관계 R의 경우 R과 관련된 카운팅 문제가 함수임

fR(x) = {y: R(x, y) } .

최적화 문제

최적화 문제는 검색 문제에 대한 가능한 모든 솔루션 집합 중에서 "최상의 가능한" 솔루션을 찾는 것을 요구한다. 한 가지 예는 최대 독립 집합 문제:

"그래프 G를 지정하면 최대 크기의 독립된 G 집합을 찾으십시오."

최적화 문제는 그들의 검색 관계에 의해 대표될 수 있다.

함수 문제

함수 문제에서는 모든 입력에 대해 하나의 출력(총함수의 출력)이 예상되지만, 결정 문제의 출력보다 출력이 더 복잡하다. 즉, 단순히 "예"나 "아니오"가 아니다. 가장 유명한 예 중 하나는 여행 세일즈맨 문제 입니다.

도시 목록과 각 도시 쌍의 거리를 감안할 때 각 도시를 정확히 한 번 방문하고 원도심으로 돌아오는 최단 경로를 찾아라.

그것은 조합 최적화의 NP-hard 문제로서, 운영 연구와 이론 컴퓨터 과학에 중요하다.

약속문제

주요기사 : 약속문제

계산 복잡성 이론에서 보통 {0, 1}*의 어떤 문자열도 문제의 계산 문제의 한 예를 나타낸다고 암묵적으로 가정한다. 그러나 때때로 모든 문자열 {0, 1}*이(가) 유효한 인스턴스를 나타내지 않으며, {0, 1)의 적절한 하위 *집합을 "유효한 인스턴스" 집합으로 지정한다. 이런 유형의 계산 문제를 약속 문제라고 한다.

다음은 약속 문제의 예다.

"그래프 G를 기준으로 G의 모든 독립형 집합이 최대 5인지, 아니면 G가 최소 10개의 독립형 집합이 있는지 확인하십시오."

여기서 유효한 예로는 최대 독립 집합 크기가 최대 5 또는 최소 10인 그래프가 있다.

의사결정 약속 문제는 보통 {0, 1}*의 분리형 하위 집합(Lyes, Lno) 쌍으로 표현된다. 유효한 예는 Lyes ∪ Lno. Lyes. L.에no 있는 경우 각각 예와 아니오로 답한 경우를 나타낸다.

약속 문제는 근사치 경도, 속성 시험 및 대화형 증명 시스템을 포함하여 계산 복잡성의 몇 가지 영역에서 중요한 역할을 한다.

참고 항목

메모들

  1. ^ 사용된 표기법에 대한 정규식 참조

참조

  • Even, Shimon; Selman, Alan L.; Yacobi, Yacov (1984), "The complexity of promise problems with applications to public-key cryptography", Information and Control, 61 (2): 159–173, doi:10.1016/S0019-9958(84)80056-X.
  • Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, ISBN 978-0-521-88473-0.
  • Goldreich, Oded; Wigderson, Avi (2008), "IV.20 Computational Complexity", in Gowers, Timothy; Barrow-Green, June; Leader, Imre (eds.), The Princeton Companion to Mathematics, Princeton University Press, pp. 575–604, ISBN 978-0-691-11880-2.