샤프-P-완전

이 문서는 위키백과의 기술적인 한계로 인하여 다른 제목을 사용합니다. 이 문서의 정확한 제목은 #P-완전입니다.

#P-완전은 계산 복잡도 이론 용어로, 복잡도 종류의 일종이다. 어떤 문제가 #P-완전이라는 것과 어떤 문제가 #P이고 모든 #P 문제가 로그 공간만 써서 그 문제로 환산될 수 있다는 것은 동치이다. (실제로는 "인색한 환산"(parsimonious reduction)이라는 더 강한 환산이 필요하다. 이 환산은 해의 개수마저도 보존한다.)

#P-완전 문제로는 이런 것이 있다:

• 주어진 DNF 식을 만족하는 변수 할당은 몇 가지인가?
• 주어진 행렬의 퍼머넌트는 무엇인가?
• 이분 그래프가 주어질 때 완벽 부합은 몇 가지인가?

#P-완전 문제를 푸는 다항 시간 알고리즘은 현재까지는 알려진 바가 없다. 만일 있다면 P = PH가 되고, 따라서 P = NP이기 때문이다. 결정론적 알고리즘 중에서는 그럴싸한 오차 범위 안으로 근사값을 구하는 것도 아직 없다.

그러나 몇몇 #P-완전에 대해 높은 확률로 좋은 근사값을 구하는 확률적 알고리즘은 존재한다. 몇몇 #P-완전 문제에는 대응하는 쉬운 P 문제가 있다. 여기에는 위에서 든 세 문제도 들어간다. 이를테면, 세 번째 문제에 대응하는 판정 문제는 "주어진 이분 그래프에 대한 완벽 부합이 있는가?"와 같은 문제이다. 꼭짓점 V개와 변 E개가 있는 그래프라면, 이 문제는 O(VE) 시간에 풀 수 있다. 완벽 부합의 개수를 세는 문제(유향 그래프에서는 순환 덮개를 세는 문제)는 퍼머넌트라고 알려져 있다.