샤프-P

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 결정 문제와의 관계
- 2.1. 예시
3. 관련 복잡도 종류
4. 공식 정의
5. 역사
참조

1. 개요

#P는 계산 복잡도 이론에서 사용되는 복잡도 종류의 하나로, NP 결정 문제에 대응하는 함수 문제들을 다룬다. NP 문제가 "해가 존재하는가?"를 묻는다면, #P 문제는 "해가 얼마나 많은가?"를 묻는다. #P 문제는 NP 문제보다 어려울 수 있으며, #P-완전 문제도 존재한다. #P 오라클을 가진 다항 시간 머신은 PH 문제를 해결할 수 있으며, PP 및 ⊕P와 같은 다른 복잡도 종류와 관련이 있다. #P는 튜링 기계 또는 검증자를 사용하여 정의할 수 있으며, 레슬리 발리언트에 의해 처음 정의되었고, 영구 계산 문제에 대한 연구와 관련이 있다.

더 읽어볼만한 페이지

복잡도 종류 - P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
복잡도 종류 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.

샤프-P
#P
종류	복잡도 종류
계산 모델	튜링 기계
완전 문제	#SAT (정확히 k개의 변수가 true인 충족 할당 수를 계산) #단방향 함수 문제 영구 계산
관련 복잡도 종류
포함	NP
포함	PH (복잡도)
포함	P#P
포함	FP#P
하드	IP (복잡도)
하드	PSPACE
샤프-P (#P)
정의	함수 문제의 복잡도 종류. 판정 문제에 대한 NP (복잡도) 복잡도 종류는 '예' 인스턴스의 존재를 묻는 반면, #P는 '예' 인스턴스 수를 계산합니다. 더 정확하게는, #P는 다항 시간 비결정적 튜링 기계 M에 대해 M이 수락하는 수락 계산의 수를 계산하는 함수 f입니다.
역사	레슬리 밸리언트가 1979년에 정의함
중요성	#P-완전 문제는 다항 시간 내에 풀 수 있다면 다항 계층이 붕괴됨. 토다 정리 참조.
예시	#SAT (CNF 수식의 만족 할당 수 계산) 그래프에서 완벽한 매칭 수 계산 그래프에서 해밀턴 회로 수 계산
참고
관련 항목	토다 정리 FP (복잡도) NP (복잡도) P (복잡도) 다항 계층

2. 결정 문제와의 관계

NP 결정 문제는 "특정 조건을 만족하는 해가 존재하는가?"라는 질문 형태로 표현되는 반면, #P 문제는 "얼마나 많은 해가 존재하는가?"를 묻는다.

2. 1. 예시

NP 결정 문제는 흔히 "특정 제약 조건을 만족하는 해가 존재하는가?"의 형태로 나타난다. 예를 들어 다음과 같은 질문들이 있다.

정수 목록의 부분 집합 중 합이 0이 되는 것이 존재하는가? (부분집합 합 문제)
주어진 그래프에서 비용이 100 미만인 해밀턴 회로가 존재하는가? (외판원 문제)
주어진 CNF (논리곱 정규 형식) 공식을 만족하는 변수 할당이 존재하는가? (불만족 문제 또는 SAT)
일변수 실수 다항식이 양의 근을 갖는가? (근 찾기)

이에 대응하는 #P 함수 문제는 "존재하는가"가 아니라 "얼마나 많은가"를 묻는다. 예를 들어 다음과 같다.

정수 목록의 부분 집합 중 합이 0이 되는 것은 얼마나 많은가?
주어진 그래프에서 비용이 100 미만인 해밀턴 회로는 얼마나 많은가?
주어진 CNF 공식을 만족하는 변수 할당은 얼마나 많은가?
일변수 실수 다항식의 양의 근은 얼마나 많은가?

3. 관련 복잡도 종류

'''#P''' 문제는 적어도 해당 '''NP''' 문제만큼 어렵다. 답을 세는 것이 쉬우면 답이 있는지 없는지 확인하는 것도 쉬울 것이다. 그냥 세어보고 0보다 큰지 확인하면 된다. 이러한 문제 중 일부, 예를 들어 근 찾기는 FP에 속할 정도로 쉬운 반면, 다른 문제들은 #P-완전이다.

토다의 정리의 결과 중 하나는 '''#P''' 오라클을 가진 다항 시간 머신 ('''P'''^'''#P''')이 '''PH''', 즉 전체 다항 시간 계층의 모든 문제를 해결할 수 있다는 것이다. 사실, 다항 시간 머신은 '''PH'''의 어떤 문제라도 해결하기 위해 단 하나의 '''#P''' 쿼리만 하면 된다. 이것은 '''#P'''-완전 문제를 정확하게 해결하는 것이 극도로 어렵다는 것을 나타낸다.

'''#P'''와 가장 가까운 결정 문제 클래스는 계산 경로의 다수 (절반 이상)가 허용되는지 묻는 '''PP'''이다. 이것은 '''#P''' 문제 답에서 가장 중요한 비트를 찾는다. 결정 문제 클래스 '''⊕P''' (Parity-P라고 발음)는 대신 '''#P''' 답변의 최하위 비트를 묻는다.

4. 공식 정의

'''#P'''는 모든 함수 $f:\{0,1\}^* \to \mathbb{N}$ 의 집합으로, 모든 $x \in \{0,1\}^*$ 에 대해 $f(x)$ 가 $x$ 에 대한 $M$ 의 계산 그래프에서 허용되는 분기의 수와 같은 다항 시간 비결정적 튜링 기계 $M$ 이 존재하는 경우를 말한다.^[1]

'''#P'''는 검증자를 사용하여 정의할 수도 있다. NP 결정 문제는 주어진 문제 인스턴스에 대해 다항 시간으로 검사 가능한 증명서가 존재하는지에 대한 것이다. 즉, '''NP'''는 입력에 대한 멤버십 증명이 존재하여 다항 시간 내에 정확성을 검사할 수 있는지 묻는다. 반면 '''#P'''는 문제 인스턴스에 대해 다항 시간 내에 검사 가능한 증명서가 "얼마나 많이" 존재하는지 묻는다.^[1] 이러한 맥락에서 '''#P'''는 다음과 같이 정의된다.

'''#P'''는 다항식 $p: \mathbb{N} \to \mathbb{N}$ 과 검증자(다항 시간 결정적 튜링 기계 $V$ )가 존재하여, 모든 $x \in \{0,1\}^*$ 에 대해 $f(x)=\Big| \big \{y \in \{0,1\}^{p(|x|)} : V(x,y)=1 \big \} \Big|$ 인 함수 $f: \{0,1\}^* \to \mathbb{N}$ 의 집합이다.^[2] 다시 말해, $f(x)$ 는 다항식 크기의 모든 증명서를 포함하는 집합의 크기와 같다.

5. 역사

'''#P''' 복잡도 종류는 1979년 레슬리 발리언트가 정사각 행렬의 영구 계산에 대한 논문에서 처음 정의했으며, 그 논문에서 영구는 #P-완전임을 증명했다.^[3]

래리 스톡마이어는 모든 #P 문제에 대해 SAT 오라클을 사용하는 무작위 알고리즘이 존재하며, 이는 높은 확률로 문제의 근삿값을 다항 시간 내에 계산할 수 있음을 증명했다.^[4] 이 알고리즘은 남은 해시 렘마를 기반으로 한다.

참조

_[1] 웹사이트 Complexity of counting https://www.cs.princ[...] Princeton University 2006
_[2] 서적 Computational Complexity: A Modern Approach Cambridge University Press 2009
_[3] 간행물 The Complexity of Computing the Permanent Elsevier 1979
_[4] 간행물 On Approximation Algorithms for #P http://www.geocities[...] 1985-11

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com