카운팅 문제(복잡성)

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "카운팅 문제" 복잡성 – 뉴스 · 신문 · 책 · 학자 · JSTOR (2014년 10월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

계산 복잡성 이론과 계산 가능성 이론에서 계산 문제는 계산 문제의 한 유형이다.R이 검색 문제인 경우

${\displaystyle c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,}$

해당 계수함수 및

${\displaystyle \#R=\{(x,y)\mid y\leq c_{R}(x)\}}$

해당 의사결정 문제를 나타낸다.

c는_R 검색 문제인 반면 #R은 의사결정 문제인 반면, c는_R 바이너리 검색을 사용하여 #R(적절한 C의 경우)로 축소될 수 있다(#R은_R c의 그래프가 되기 보다는, 이 바이너리 검색을 가능하게 하기 위한 것이다).

계산 복잡도 클래스

NX가 비결정론적 시스템과 관련된 복잡도 클래스인 경우 #X = {#R R ∈ NX}은(는) NX의 각 검색 문제와 관련된 카운트 문제 집합이다.특히 #P는 NP 검색 문제와 관련된 문제집계 등급이다.NP가 다수의 1개 감축을 통해 NP 완성 문제를 가지고 있듯이, #P는 해결책의 수를 보존하는 단순화 감소, 문제 변환을 통해 완전한 문제를 가지고 있다.

참고 항목

• GapP

외부 링크

• "counting problem". PlanetMath.
• "counting complexity class". PlanetMath.