샤프-P-완전
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 #P-완전은 복잡도 종류의 일종이다. 어떤 문제가 #P-완전이라는 것과, 어떤 문제가 #P이고 모든 #P 문제가 로그 공간만 써서 그 문제로 환산될 수 있다는 것은 동치이다. (실제로는 "인색한 환산"(parsimonious reduction)이라는 더 강한 환산이 필요하다. 이 환산은 해의 개수마저도 보존한다.)
#P-완전 문제로는 이런 것이 있다:
#P-완전 문제를 푸는 다항 시간 알고리즘은 없을 것으로 보인다. 있다면 P = PH가 되고, 따라서 P = NP이기 때문이다. 정확하게 푸는 게 불가능하다면, 근사해서 풀 수는 있을까? 결정론적 알고리즘 중에서는 그럴싸한 오차 범위 안으로 근사값을 구하는 것도 아직 없다.
그러나 몇몇 #P-완전에 대해 높은 확률로 좋은 근사값을 구하는 확률적 알고리즘은 존재한다. 이것은 확률적 알고리즘의 위력을 보여주는 인상적인 예이다.
놀랍게도 몇몇 #P-완전 문제에는 대응하는 쉬운 P 문제가 있다. 여기에는 위에서 든 세 문제도 들어간다. 이를테면, 세 번째 문제에 대응하는 판정 문제는 "주어진 이분 그래프에 대한 완벽 매칭이 있는가?" 하는 문제이다. 꼭지점 V개와 변 E가 있는 그래프라면, 이 문제는 O(VE) 시간에 풀 수 있다. 완벽 매칭의 개수를 세는 문제(유향 그래프에서는 사이클 커버를 세는 문제)는 퍼머넌트라고 알려져 있다.
| 주요 복잡도 종류 (더 보기) |
|---|
|
P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C |
