♯P

♯P
이 글의 정확한 제목은 #P이다. #의 대체는 기술적 제약에 기인한다.

계산 복잡성 이론에서 복잡성 등급 #P("sharp P" 또는 때로는 "number P" 또는 "hash P"로 발음되는)는 설정된 NP의 의사결정 문제와 관련된 계산 문제의 집합이다. 좀 더 공식적으로, #P는 "compute f(x)" 형태의 기능 문제의 등급이며, 여기서 f는 다항식 시간에 실행되는 비계수 튜링 기계의 수용 경로 수입니다. 대부분의 잘 알려진 복잡성 등급과는 달리, 그것은 의사결정 문제의 등급이 아니라 기능 문제의 등급이다. 이 수업에서 가장 어렵고 대표적인 문제는 #P-완전이다.

의사결정 문제와 관련

NP 의사결정 문제는 종종 "특정 제약조건을 충족하는 해결책이 있는가?"라는 형식이다. 예를 들면 다음과 같다.

해당 #P 함수 문제는 "있느냐"가 아니라 "몇 개인가"를 묻는다. 예를 들면 다음과 같다.

  • 정수 목록의 하위 집합이 0에 얼마나 추가되나?
  • 주어진 그래프에 100 미만의 비용이 든 해밀턴 사이클은 몇 개인가?
  • 주어진 CNF 공식을 충족하는 변수 할당 수
  • 일변량 실제 다항식의 뿌리는 얼마나 많은 양수인가?

관련 복잡도 클래스

분명히 #P 문제는 적어도 해당 NP 문제만큼 어려워야 한다. 답을 세는 것이 쉽다면, 답이 있는지 구별하는 것이 쉬워야 한다. 단지 세기만 하고 세는 것이 0보다 큰지 알아보자. 뿌리 찾기 등 이 문제들 중 일부는 FP에 있을 수 있을 정도로 쉬운 반면, 다른 것들은 #P-완전하다.

토다 정리의 한 가지 결과는 #P 신탁(P#P)을 가진 다항식 시간 기계는 전체 다항식 계층 구조인 PH의 모든 문제를 해결할 수 있다는 것이다. 실제로 다항식 타임머신은 PH의 어떤 문제를 해결하기 위해 하나의 #P 질의만 하면 된다. 이는 #P-완전한 문제를 정확하게 풀어나가는 극도의 난이도를 나타내는 것이다.

놀랍게도 어렵다고 판단되는 일부 #P 문제는 쉬운(예: 선형 시간) P 문제에 대응한다. 자세한 내용은 #P 완료를 참조하십시오.

#P에 가장 가까운 의사결정 문제 등급은 PP로, 계산 경로의 과반수(반수 이상)가 수용하는지 여부를 묻는다. 이것은 #P 문제 답변에서 가장 중요한 부분을 찾아낸다. 의사결정 문제 클래스 ⊕P("Parity-P"로 발음됨)는 대신 #P 답의 최하위 부분을 요구한다.

형식 정의

#P는 공식적으로 다음과 같이 정의된다.

#P is the set of all functions such that there is a polynomial time nondeterministic Turing machine such that for all , equals the number of acce를M {\ M의 계산 로x {\[1]x에 pting.

#P는 또한 진충의 용어로 동등하게 정의될 수 있다. 결정 문제는 특정 문제 인스턴스에 대한 다항식 시간 검사 가능 인증서(즉, NP는 다항식 시간에 정확성을 확인할 수 있는 입력에 대한 구성원 자격 증명이 있는지 여부를 묻는 경우 NP에 있다. 클래스 #P는 다항식 시간에 정확성을 확인할 수 있는 문제 인스턴스에 대해 얼마나 많은 인증서가 존재하는지 묻는다.[1] 이 맥락에서 #P는 다음과 같이 정의된다.

#P is the set of functions such that there exists a polynomial and a polynomial-time deterministic Turing machine , called the verifier, such that for every }∗{\displaystylex\in\와 같이{0,1\}^{*}}, f())){y∈{0,1}p()):V(), y)=1}{\displaystyle f())={\Big}{\big\와 같이{}y\in \{0,1\}^{p())}:V(x, y)=1{\big)}}{\Big}}집합이 모든 그 polynomial-size'ce'포함하는의 크기와 같(즉, f()){\displaystyle f())}.[2].rti수식어

역사

복잡도 등급 #P는 레슬리 발리안트가 1979년 정사각형 행렬의 영구적 계산에 관한 논문에서 처음 정의한 것으로, 영구성이 #P-완전하다는 것을 증명했다.[3]

래리 Stockmeyer은 모든 # P문제 P에{P\displaystyle}이 무작위 알고리즘 SAT, P{P\displaystyle}과ϵ의 한{\displaystyle}인스턴스를 고려하기 위해 신탁을 사용하여 존재하고 높은 확률과 0{\displaystyle \epsilon>0}을 반환 수){\displaystyle)}등이 입증되었다. 그 -) ( ) x ( + ) () [4]. 알고리즘의 런타임은 과 1 /{\ 1}의 다항식이며, 알고리즘은 남은 해시 보조정리기를 기반으로 한다

참고 항목

참조

  1. ^ Jump up to: a b Barak, Boaz (Spring 2006). "Complexity of counting" (PDF). Computer Science 522: Computational Complexity. Princeton University.
  2. ^ Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge University Press. p. 344. ISBN 978-0-521-42426-4.
  3. ^ Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science. Elsevier. 8 (2): 189–201. doi:10.1016/0304-3975(79)90044-6.
  4. ^ Stockmeyer, Larry (November 1985). "On Approximation Algorithms for #P" (PDF). SIAM Journal on Computing. 14 (4): 849. doi:10.1137/0214060. Archived from the original (PDF) on 2009. Lay summary.

외부 링크