복잡도 종류

3. 복잡도 종류

복잡도 종류는 관련된 계산 문제들의 집합이다. 계산 복잡도 이론에서 다루는 문제(혹은 언어나 문법)의 종류는 아래 표와 같이 정리할 수 있다.

결정적 튜링 기계(DTM)는 비결정적 튜링 기계(NTM)의 변형이다. NTM은 주어진 상태에서 여러 가능한 미래 행동을 탐색하고, 수락하는 분기(수락하는 분기가 있는 경우)를 "선택"할 수 있는 기능을 추가한 일반적인 튜링 기계이다. DTM은 단 하나의 계산 분기만을 따라야 하는 반면, NTM은 각 단계에서 여러 가능한 계산 경로로 분기되는 계산 트리로 생각할 수 있다. 트리의 적어도 하나의 분기가 "수락" 조건으로 정지하면 NTM은 입력을 수락한다.

NTM의 시간 복잡도는 NTM이 계산의 ''어떤'' 분기에서 사용하는 최대 단계 수이며, 공간 복잡도는 NTM이 계산의 어떤 분기에서 사용하는 최대 셀 수이다. DTM은 비결정성의 힘을 사용하지 않는 NTM의 특별한 경우이므로, DTM에 의해 수행될 수 있는 모든 계산은 동등한 NTM에 의해서도 수행될 수 있다. 또한 DTM을 사용하여 모든 NTM을 시뮬레이션하는 것이 가능하다.

다음 표는 계산 복잡도 이론 내에서 다루는 몇 가지 문제(또는 문법, 언어)의 클래스를 시각적으로 표현한 것이다.

각 복잡도 클래스에는 보문제의 집합인 'Co'가 붙은 클래스가 존재한다.^[1] 예를 들어, 문제 L이 NP에 포함된다면, 그 보문제는 Co-NP에 속한다.^[1]

3. 1. 시간 복잡도 종류

3. 2. 공간 복잡도 종류

:$\backslash mathsf\{L\}\; =\; \backslash mathsf\{DSPACE\}(\backslash log\; n)$

:$\backslash mathsf\{NL\}\; =\; \backslash mathsf\{NSPACE\}(\backslash log\; n)$

$\backslash mathsf\{L\}\backslash subseteq\backslash mathsf\{NL\}\backslash subseteq\backslash mathsf\{P\}$임이 알려져 있지만, 이 관계들이 실제로 포함관계인지는 아직 밝혀지지 않았다.

'''PSPACE'''와 '''NPSPACE'''는 각각 '''P'''와 '''NP'''의 공간 복잡도에 대응하는 개념이다. '''PSPACE'''는 결정적 튜링 기계로 다항식 공간 안에 풀 수 있는 문제들의 집합이며, '''NPSPACE'''는 비결정적 튜링 기계로 다항식 공간 안에 풀 수 있는 문제들의 집합이다. 공식적으로는 다음과 같다.

:$\backslash mathsf\{PSPACE\}\; =\; \backslash bigcup\_\{k\backslash in\backslash mathbb\{N\}\}\; \backslash mathsf\{DSPACE\}(n^k)$

:$\backslash mathsf\{NPSPACE\}\; =\; \backslash bigcup\_\{k\backslash in\backslash mathbb\{N\}\}\; \backslash mathsf\{NSPACE\}(n^k)$

새비치의 정리에 의해 '''PSPACE'''='''NPSPACE'''임이 증명되었다. 또한 $\backslash mathsf\{P\}\; \backslash subseteq\; \backslash mathsf\{PSPACE\}$임이 알려져 있는데, 이는 튜링 기계가 테이프에 셀을 쓰는 데 1단위 시간이 걸린다고 가정하면, 다항 시간 내에 작동하는 튜링 기계는 다항식 개수의 셀에만 쓸 수 있기 때문이다. '''P'''가 '''PSPACE'''의 진부분집합일 것으로 추측되지만, 아직 증명되지는 않았다.

'''EXPSPACE'''와 '''NEXPSPACE'''는 각각 '''EXPTIME'''과 '''NEXPTIME'''의 공간 복잡도에 대응하는 개념이다. '''EXPSPACE'''는 결정적 튜링 기계로 지수 공간 안에 해결 가능한 문제들의 집합이며, '''NEXPSPACE'''는 비결정적 튜링 기계로 지수 공간 안에 해결 가능한 문제들의 집합이다. 공식적으로는 다음과 같다.

:$\backslash mathsf\{EXPSPACE\}\; =\; \backslash bigcup\_\{k\backslash in\backslash mathbb\{N\}\}\; \backslash mathsf\{DSPACE\}(2^\{n^k\})$

:$\backslash mathsf\{NEXPSPACE\}\; =\; \backslash bigcup\_\{k\backslash in\backslash mathbb\{N\}\}\; \backslash mathsf\{NSPACE\}(2^\{n^k\})$

새비치 정리에 의해 '''EXPSPACE'''='''NEXPSPACE'''이다. 이 종류는 매우 광범위하며, '''PSPACE''', '''NP''', '''P'''의 진부분집합으로 알려져 있고, '''EXPTIME'''의 진부분집합일 것으로 예상된다.

3. 3. 확률적 복잡도 종류

확률적 튜링 기계를 사용하여 정의되는 중요한 복잡도 종류에는 ZPP, RP, co-RP, BPP, PP가 있다. 확률적 튜링 기계는 무작위 동전을 던질 수 있는 튜링 기계의 변형이다. 이러한 종류는 확률적 알고리즘의 복잡성을 더 잘 설명하는 데 도움이 된다.

확률적 튜링 기계는 각 단계에서 여러 전이 함수 중 하나를 확률적으로 선택한다는 점을 제외하면 결정적 튜링 기계와 유사하다. 표준 정의에서는 두 개의 전이 함수를 사용하며, 이는 동전 던지기와 유사하게 각 단계에서 어떤 함수를 선택할지 결정한다. 계산 단계마다 무작위성이 도입되므로 오류가 발생할 수 있다. 즉, 튜링 기계가 받아들여야 하는 문자열이 거부되거나, 거부해야 하는 문자열이 받아들여질 수 있다. 따라서 확률적 튜링 기계를 기반으로 하는 복잡도 종류는 허용되는 오류의 양($\backslash epsilon$)을 중심으로 정의된다. 확률적 튜링 기계 $M$이 언어 $L$을 오류 확률 $\backslash epsilon$으로 인식한다는 것은 다음을 의미한다.

# $L$에 있는 문자열 $w$에 대해, $\backslash text\{Pr\}[M\; \backslash text\{\; accepts\; \}\; w]\; \backslash geq\; 1\; -\; \backslash epsilon$

# $L$에 없는 문자열 $w$에 대해, $\backslash text\{Pr\}[M\; \backslash text\{\; rejects\; \}\; w]\; \backslash geq\; 1\; -\; \backslash epsilon$

• '''ZPP''' (Zero-error Probabilistic Polynomial time): 오류 확률이 0인 확률적 튜링 머신으로 다항 시간에 풀 수 있는 문제의 집합이다. 어떠한 오류도 허용하지 않으므로 가장 엄격한 확률적 문제 클래스이다.

• '''RP''' (Randomized Polynomial time): 언어에 속하지 않는 문자열에 대해서는 오류가 없지만, 언어에 속하는 문자열에 대해서는 제한된 오류를 허용하는 문제의 집합이다. 문자열이 언어에 속하지 않으면 항상 거부하고, 속하면 최소 1/2의 확률로 허용하는 확률적 다항 시간 튜링 머신 $M$이 존재한다.

• '''co-RP''': RP와 반대로, 언어에 속하는 문자열에 대해서는 오류가 없지만, 속하지 않는 문자열에 대해서는 오류를 허용한다.

'''RP'''와 '''co-RP'''는 일방적 오류를 가진 확률적 튜링 머신으로 해결 가능한 모든 문제를 포함한다.

• '''BPP''' (Bounded-error Probabilistic Polynomial time): 양방향 오류를 허용하며, 오류 확률이 1/3 미만인 확률적 튜링 머신으로 다항 시간에 해결 가능한 문제의 집합이다. '''BPP'''는 실제 컴퓨터에서 빠르게 실행 가능한 효율적인 랜덤화된 알고리즘을 가진다는 점에서 실용적인 관련성이 높다. '''P=BPP'''인지 여부는 컴퓨터 과학의 중요한 미해결 문제이며, 만약 참이라면 무작위성이 컴퓨터의 계산 능력을 증가시키지 않는다는 것을 의미한다.

• '''PP''' (Probabilistic Polynomial time): 모든 문자열에 대해 1/2 미만의 오류 확률로 다항 시간 내에 확률적 튜링 머신으로 해결 가능한 언어의 집합이다.

'''ZPP''', '''RP''', '''co-RP'''는 모두 '''BPP'''의 부분집합이며, '''BPP'''는 '''PP'''의 부분집합이다. '''ZPP'''는 '''RP'''와 '''co-RP''' 모두에 속하는 문제로 구성된다 ($\backslash textsf\{ZPP\}=\backslash textsf\{RP\}\backslash cap\backslash textsf\{co-RP\}$). 이는 '''RP'''와 '''co-RP'''가 일방적 오류만 허용하기 때문이다.

양자 정보 과학에서 중요한 '''BQP'''와 '''QMA''' 클래스는 양자 튜링 기계를 사용하여 정의된다.

3. 4. 기타 복잡도 종류

#P는 NP 문제의 해를 세는 문제의 집합이다. IP는 대화형 증명 시스템으로 다항 시간 안에 풀 수 있는 문제의 집합이다. NC는 병렬 컴퓨터에서 효율적으로 해결할 수 있는 문제의 집합이다.

다음은 기타 복잡도 종류를 나열한 것이다.

복잡도 종류	설명
#P	NP 문제의 해를 세는 문제[1]
#P-완전	#P 중에서 가장 어려운 문제군[1]
AH	산술적 계층[1]
AP	교대 튜링 머신으로 다항 시간 안에 풀 수 있는 문제의 클래스[1]
BPP	난수 알고리즘으로 다항 시간 안에 풀 수 있는 문제의 클래스 (해는 아마도 옳다)[1]
BQP	양자 컴퓨터로 다항 시간 안에 풀 수 있는 문제의 클래스 (해는 아마도 옳다)[1]
Co-NP	비결정적 기계로 "NO"임을 다항 시간 안에 결정할 수 있는 문제의 클래스[1]
Co-NP-완전	Co-NP 중에서 가장 어려운 문제군[1]
DSPACE(f(n))	결정적 기계로 공간 복잡도 O(f(n))로 풀 수 있는 문제의 클래스[1]
DTIME(f(n))	결정적 기계로 시간 복잡도 O(f(n))로 풀 수 있는 문제의 클래스[1]
E	선형 지수의 지수 함수 시간으로 풀 수 있는 문제의 클래스 (밑을 2로 하는 DTIME(2O(n))와 등가)[1]
ESPACE	선형 지수의 지수 함수 영역으로 풀 수 있는 문제의 클래스[1]
EXPSPACE	지수 함수 영역으로 풀 수 있는 문제의 클래스[1]
EXPTIME	지수 함수 시간으로 풀 수 있는 문제의 클래스[1]
ELEMENTARY	지수 계층에 속하는 문제의 클래스 (루프 깊이가 2 이하인 루프 프로그램으로 풀 수 있는 문제의 클래스)[1]
IP	대화형 증명 시스템으로 다항 시간 안에 풀 수 있는 문제의 클래스[1]
L	로그 영역으로 풀 수 있는 문제의 클래스[1]
LOGCFL	문맥 자유 언어로 환원 가능한 로그 영역으로 풀 수 있는 문제의 클래스[1]
NC	병렬 컴퓨터에서 효율적으로 풀 수 있는 문제의 클래스 (O((log n)c))[1]
NEXPTIME	비결정적 기계로 지수 함수 시간으로 풀 수 있는 문제의 클래스[1]
NL	비결정적 튜링 머신으로 로그 영역으로 풀 수 있는 문제의 클래스[1]
NP	비결정적 튜링 머신으로 다항 시간 안에 풀 수 있는 문제의 클래스 (P≠NP 추측도 참조). 해에 대해 다항 길이의 증거(witness)가 존재하고, 해의 후보와 증거가 주어졌을 때 검증이 결정적 튜링 머신으로 다항 시간 안에 풀 수 있는 문제의 클래스와 일치한다.[1]
NP-완전	NP 중에서 가장 어려운 문제의 클래스[1]
NP-hard	NP-완전보다 더 어려운 문제의 클래스[1]
NSPACE(f(n))	비결정적 기계로 공간 복잡도 O(f(n))로 풀 수 있는 문제의 클래스[1]
NTIME(f(n))	비결정적 기계로 시간 복잡도 O(f(n))로 풀 수 있는 문제의 클래스[1]
P	다항 시간 안에 풀 수 있는 문제의 클래스[1]
P-완전	P 중에서 가장 어려운 문제의 클래스이며, 병렬 컴퓨터로 풀 수 있다.[1]
PH	다항식 계층에 있는 클래스 군의 합집합[1]
PP	확률적으로 다항 시간 안에 풀 수 있는 문제의 클래스 (해가 옳을 가능성이 2분의 1보다 약간 큼)[1]
PR	원시 재귀 함수로 풀 수 있는 문제의 클래스[1]
PSPACE	다항식 영역으로 풀 수 있는 문제의 클래스[1]
PSPACE-완전	PSPACE 중에서 가장 어려운 문제군[1]
R	유한 시간 안에 풀 수 있는 문제의 클래스. 튜링 머신으로 풀 수 있는 모든 문제의 집합이며, 귀납 언어에 해당[1]
RE	"YES"이면 정지하고 "NO"이면 정지하지 않는 튜링 머신이 존재하는 문제의 클래스. 귀납적 가산 언어에 해당한다. 해에 대해 증거(witness)가 존재하고, 해의 후보와 증거가 주어졌을 때 검증이 튜링 머신으로 풀 수 있는 문제의 클래스와 일치한다.[1]
RP	난수 알고리즘으로 다항 시간 안에 풀 수 있는 문제의 클래스 (해의 NO인 경우에 옳지 않을 수 있지만, YES인 경우 옳다)[1]
UP	비결정적 튜링 머신으로 다항 시간 안에 풀 수 있는 결정 문제의 클래스 (P와 NP의 중간)[1]
ZPP	난수 알고리즘으로 풀 수 있는 문제의 클래스 (해는 항상 옳지만, 평균적으로 다항 시간이 걸린다)[1]

각 복잡도 클래스에는 보문제의 집합인 'Co'가 붙은 클래스가 존재한다.^[1] 예를 들어, 문제 L이 NP에 포함된다면, 그 보문제는 Co-NP에 속한다.^[1]

4. 복잡도 종류 사이의 관계

복잡도 이론에서 다루는 문제(혹은 언어나 문법)의 종류는 아래 표와 같이 정리할 수 있다. 어떤 복잡도 종류 '''X'''가 '''Y'''의 진부분집합이면, '''X'''는 '''Y''' 아래에 검은 실선으로 연결했다. 만약 '''X'''가 '''Y'''의 부분집합이지만 두 집합이 같은지 아닌지 아직 알려지지 않았으면, 점선으로 연결했다.

엄밀하게 말하면, 풀 수 있는 문제와 풀 수 없는 문제를 구분하는 것은 계산 복잡도 이론이 아니라 계산 가능성 이론에 속하지만, 전체적인 관계를 설명하기 위해 아래 표에 포함시켰다.

복잡도 종류는 다양한 폐포 속성을 가진다. 예를 들어, 결정 종류는 부정, 논리합, 논리곱 또는 모든 불 연산에 대해 닫혀 있을 수 있다. 또한 다양한 양화 방식에 대해서도 닫혀 있을 수 있다. 예를 들어, '''P'''는 모든 불 연산과 다항식 크기 도메인에 대한 양화에 대해 닫혀 있다. 폐포 속성은 종류를 분리하는 데 유용할 수 있다. 두 복잡도 종류를 분리하는 한 가지 방법은 한 종류에는 있지만 다른 종류에는 없는 특정 폐포 속성을 찾는 것이다.

부정에 대해 닫혀 있지 않은 각 종류 '''X'''는 보완 종류 '''co-X'''를 갖는다. 이는 '''X'''에 포함된 언어의 보완 언어로 구성된다(즉, $\backslash textsf\{co-X\}\; =\; \backslash \{L|\; \backslash overline\{L\}\; \backslash in\; \backslash mathsf\{X\}\; \backslash \}$). 예를 들어, '''co-NP'''는 중요한 보완 복잡도 종류 중 하나이며, '''co-NP'''='''NP'''인지에 대한 미해결 문제의 중심에 있다.

4. 1. 포함 관계

• P는 NP의 부분집합이다. (P ⊆ NP)
• NP는 PSPACE의 부분집합이다. (NP ⊆ PSPACE)
• PSPACE는 EXPTIME의 부분집합이다. (PSPACE ⊆ EXPTIME)
• EXPTIME은 NEXPTIME의 부분집합이다. (EXPTIME ⊆ NEXPTIME)
• NEXPTIME은 EXPSPACE의 부분집합이다. (NEXPTIME ⊆ EXPSPACE)

4. 2. 계층 정리

4. 3. 새비치의 정리