계산 복잡도 이론

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

계산 복잡도 이론(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 문제[편집]