샤프-P
계산 복잡도 이론에서 복잡도 종류 #P는 개수를 세는 문제들로 이루어진 집합으로, 여기에 들어 있는 문제는 NP에 속한 판정 문제와 연관된다. 다른 복잡도 종류하고 다르게 #P는 판정문제가 아니라 함수 문제의 집합이다.
#P는 '샤프 피(sharp-P)'라고 읽는다. 어떤 문서에서는 '넘버 피(number-P)'라고 읽기도 한다.
NP문제는 "특정한 제약조건을 만족하는 해가 있는가?" 하는 형식인 경우가 많다. 예:
- 주어진 정수 집합에 원소의 합이 0인 부분집합이 있는가? (부분집합 합 문제)
- 주어진 그래프에서 비용이 100보다 작은 해밀턴 순환이 있는가? (외판원 문제)
- 주어진 CNF 식을 만족하는 논리값이 있는가? (충족 가능성 문제)
여기에 대응하는 #P문제는 해가 '있는지'를 묻지 않고 '몇 개인지'를 묻는다. 예:
- 주어진 정수 집합에서 원소의 합이 0인 부분집합은 몇 개인가?
- 주어진 그래프에서 비용이 100보다 작은 해밀톤 회로가 몇 개인가?
- 주어진 CNF 식을 만족하는 논리값이 몇 개인가?
좀 더 공식적으로 정의하면, #P는 "f(x)를 계산"하는 꼴로 된 함수문제의 집합이다. 여기서 f는 NP 기계가 받아들이는 경로 개수를 뜻한다.
#P 문제는 적어도 대응하는 NP 문제만큼 어려워야 한다는 것은 쉽게 알 수 있다. 답이 몇 개인지 쉽게 셀 수 있다면 답이 있는지 없는지도 쉽게 알 수 있다. 개수를 세어서 0보다 큰지만 살피면 된다. 따라서 NP-완전 문제에 대응하는 #P 문제는 반드시 NP-난해 문제가 된다.
놀랍게도 어떤 #P 문제는 대응하는 문제가 P 문제라도 어려운 경우가 있다. (정확히 말하면, 어렵다고 추측하는 것이다. 아직 P-NP 문제가 해결되지 않았으니까.) 이러한 문제에 관한 내용은 #P-완전에 있다.
#P에 가장 가까운 판정 문제 종류는 다수(과반수)인 계산 경로를 받아들였는지를 묻는 PP이다. 이것은 #P 문제가 내는 답의 최상위 비트를 찾는다. 판정 문제 종류 중 ⊕P는 최하위 비트를 찾는다.
토다 정리(Toda's theorem, (일본어: 戸田誠之助 도다 세이노스케[*])의 이름을 땄다)에서 나오는 결론 중 하나는, #P 신탁이 있는 다항 시간 기계(P#P)는 PH에 속하는 모든 문제를 풀 수 있다는 것이다. 여기서 PH는 다항 계층에 속하는 모든 복잡도 종류의 합집합이다. 실제로 다항 시간 기계는 PH에 속한 어떤 문제라도 #P 질의 하나만으로 풀어낼 수 있다. 이런 까닭에 #P-완전 문제를 정확히 풀기는 엄청나게 어려울 것으로 미루어 볼 수 있다.
외부 링크 편집
- (영어) ZPP - 복잡도 동물원