PSPACE
From Wikipedia, the free encyclopedia
계산 복잡도 이론에서 PSPACE는 결정론적 튜링 기계나 비결정론적 튜링 기계가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 판정 문제들의 집합이다. 사비치 정리에 따르면 PSPACE는 NSPACE와 같기 때문에 튜링 기계가 결정론적이든 비결정론적이든 상관 없다.
문맥-민감 언어가 PSPACE의 진부분집합이다. 복잡도 종류 NL, P, NP, PSPACE, EXPSPACE가 갖는 관계는 이렇다:
첫째 줄에 (부분집합) 기호가 세 개 있다. 셋 중 하나는
여야 하는데, 정확히 어느 것이 그런지는 알려진 바 없다. 수많은 사람들이 셋 모두
라고 추측하고 있다. P-NP 문제(두 번째
가
인지 아닌지 묻는 문제)에 대한 해법에는 상금 백만 달러가 걸려 있다.
PSPACE에서 가장 어려운 문제들을 PSPACE-완전이라고 한다. PSPACE이고 NP는 아닐 것으로 예상되는 문제들을 알고 싶으면 PSPACE-완전을 보라.