계산 복잡도 이론

계산 복잡도 이론(計算 複雜度 理論, 영어: Computational complexity theory)은 컴퓨터 과학에서 계산 이론의 분야로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임을 구성하는 방법을 연구한다. 이 때 알고리즘의 수행은 실제 컴퓨터가 할 수 있지만, 평가하는 데에는 튜링 기계와 관련이 있는 정량화된 방법을 사용한다.

복잡도의 기준은 알고리즘이 소모하는 소요 시간과 메모리 사용량 등의 자원이다. 전자를 시간 복잡도, 후자를 공간 복잡도라 한다. 일반적으로 이와 같은 시공간 등의 자원은 입력의 크기에 의존하는 것으로 취급한다.

복잡도 모형

 이 부분의 본문은 튜링 기계입니다.

알고리즘의 수행은 일반적으로 튜링 기계와 그 변종을 기준으로 한다.

대문자 O 표기법

 이 부분의 본문은 점근 표기법입니다.

점근 표기법은 복잡도를 표기하는 주된 방법이다.

복잡도 종류

 이 부분의 본문은 복잡도 종류입니다.

복잡도 종류는 시간 복잡도와 공간 복잡도를 포괄하는 문제의 집합이다. 어떤 복잡도 종류의 정의는 다음과 관련이 있다.

• 일정 복잡도를 요구하는 추상 기계의 모형. 결정론적 튜링 기계, 비결정론적 튜링 기계, 양자적 튜링 기계, 모노톤 회로 등.
• 문제의 종류. 결정, 함수, 셈, 최적화 등.

복잡도를 정의하는 주된 방법은 다음과 같다.

복잡도 정의	수행 기계 모형	자원	제한
DTIME(f(n))	결정론적 튜링 기계	시간	O(f(n))
NTIME(f(n))	비결정론적 튜링 기계	시간	O(f(n))
DSPACE(f(n))	결정론적 튜링 기계	공간	O(f(n))
NSPACE(f(n))	비결정론적 튜링 기계	공간	O(f(n))

주요 복잡도들은 다음과 같이 정의된다. (p(n)은 입력 크기 n에 관한 다항식이다.)

복잡도 종류	뜻
NEXPSPACE	NSPACE(2p(n))
EXPSPACE	DSPACE(2p(n))
NEXPTIME	NTIME(2p(n))
EXPTIME	DTIME(2p(n))
NPSPACE	NSPACE(p(n))
PSPACE	DSPACE(p(n))
NP	NTIME(p(n))
P	DTIME(p(n))
NL	NSPACE(log(p(n)))
L	DSPACE(log(p(n)))

문제들

P-NP 문제

 이 부분의 본문은 P-NP 문제입니다.

외부 링크

• “Computational complexity classes”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.