조언(복잡성)

Advice (complexity)

계산 복잡성 이론에서 조언 문자열은 입력의 길이 n에 의존할 수 있지만 입력 자체에 의존할 수는 없는 튜링 기계에 대한 추가 입력이다.결정 문제는 복합 등급 P/f(n)에 다음과 같은 속성이 있는 다항 시간 튜링 기계 M이 있는 경우: n에 대해서는 길이 f(n)의 조언 문자열 A가 있어서 길이 n의 입력 x에 대해서는 기계 M이 주어진 x와 A에 대해 정확하게 문제를 결정한다.

조언을 포함하는 가장 일반적인 복잡도 등급은 P/poly인데, 여기서 조언 길이 f(n)가 n. P/poly는 모든 n에 대해 모든 길이의 입력에 대해 문제를 정확하게 결정하는 다항 크기 부울 회로가 존재하는 의사결정 문제의 등급과 같다.등가성의 한 방향은 쉽게 알 수 있다.n마다 문제를 결정하는 다항식 크기 부울 회로 A(n)가 있다면, 우리는 어드바이저 문자열을 회로에 대한 설명으로 해석하는 튜링 기계를 사용할 수 있다.그런 다음, 권고사항으로 A(n)의 설명을 고려할 때, 기계는 길이 n의 모든 입력에 대한 문제를 정확하게 결정할 것이다.다른 방향은 쿡의 정리 증명에서와 같이 다항식 크기 회로에 의한 다항식 시간 튜링 기계의 시뮬레이션을 사용한다.조언으로 튜링 기계를 시뮬레이션하는 것은 조언 문자열이 회로에 통합될 수 있기 때문에 일반 기계를 시뮬레이션하는 것만큼 복잡하지 않다.[1]

이러한 동등성 때문에 P/poly는 다항식 크기 부울 회로 또는 다항식 크기 부울 회로로 해결할 수 있는 의사결정 문제의 등급으로 정의되기도 한다.

P/폴리에는 P와 BPP(어들만의 정리)가 모두 들어 있다.그것은 또한 모든 미해결 문제의 단항 버전과 같은, 미해결 문제의 일부 미해결 문제를 포함하고 있다.그 때문에 어떤 f에 대해서도 DTIME(f(n) 또는 NTIME(f(n))에 포함되지 않는다.

조언 클래스는 P 대신 다른 리소스 한계에 대해 정의될 수 있다.예를 들어, 길이 f(n)의 조언과 함께 비결정론적 다항식 시간 튜링 기계를 택하면 복잡도 등급 NP/f(n)가 된다.만약 우리에게 길이 2의n 조언이 허락된다면, 우리는 길이 n의 각 입력이 언어에 포함되어 있는지 여부를 인코딩하는 데 그것을 사용할 수 있다.따라서 어떤 부울함수는 길이 2의n 조언으로 계산할 수 있으며 지수 길이 이상의 조언은 의미가 없다.

마찬가지로, L/폴리 등급은 다항식 조언의 양과 함께 결정론적 로그 공간으로 정의할 수 있다.

알려진 결과는 다음과 같다.

  • NL/폴리 클래스와 UL/폴리 클래스는 같다. 즉, 조언을 포함하는 비결정론적 로그 공간 계산은 모호하지 않게 할 수 있다.[2]이것은 격리 보조정리기를 사용하여 증명될 수 있다.[3]
  • NEXP/폴리에는 coNExP가 포함된 것으로 알려져 있다.[4]
  • NP가 P/poly에 포함되면 다항 시간 계층이 붕괴된다(Karp-Lipton 정리).

참조

  1. ^ Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, p. 113, ISBN 9780521424264, Zbl 1193.68112.
  2. ^ Reinhardt, Klaus; Allender, Eric (2000). "Making nondeterminism unambiguous". SIAM J. Comput. 29 (4): 1118–1131. CiteSeerX 10.1.1.55.3203. doi:10.1137/S0097539798339041. Zbl 0947.68063.
  3. ^ Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002). The complexity theory companion. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 3-540-67419-5. Zbl 0993.68042.
  4. ^ 랜스 포트나우, 작은 정리