PSPACE (r1)

P와 NP, co-NP는 모두 PSPACE에 포함된다. 이는 다항식 시간 내에 해결 가능한 문제(P)나 검증 가능한 문제(NP)는 그 과정에서 사용하는 공간 역시 다항식을 초과할 수 없기 때문이다. 따라서 P ⊆ NP ⊆ PSPACE와 P ⊆ co-NP ⊆ PSPACE라는 포함 관계가 성립한다.

PSPACE와 NP의 관계에서 중요한 점은 NP가 PSPACE의 진부분집합인지, 즉 NP ⊊ PSPACE인지 여부는 아직 증명되지 않은 열린 문제라는 것이다. 만약 NP = PSPACE라면, NP에 있는 모든 문제를 다항식 공간으로 해결할 수 있지만, 여전히 다항식 시간 내에 해결할 수 있는지는 알 수 없다. 현재까지의 연구는 NP ≠ PSPACE일 것이라고 추측하고 있다.

co-NP와의 관계도 유사하다. co-NP는 NP 문제의 보수(complement) 문제들의 클래스이다. PSPACE는 자신의 보수 클래스인 co-PSPACE와 동일하다는 것이 알려져 있다. 즉, PSPACE = co-PSPACE이다. 이는 사빅치 정리에 의해 PSPACE와 NPSPACE가 동일하다는 사실로부터 유도될 수 있다. 반면, NP = co-NP인지는 중요한 미해결 문제 중 하나이다.

종합하면, P, NP, co-NP는 모두 PSPACE 내에 존재하며, 이들 사이의 엄밀한 포함 관계는 계산 복잡도 이론의 핵심적인 미해결 문제들로 남아 있다. PSPACE는 이들 클래스보다 더 넓은, 즉 더 어려운 문제들을 포괄하는 공간 복잡도 클래스로 이해된다.

다항식 계층(Polynomial Hierarchy, PH)는 NP와 co-NP를 일반화한 복잡도 클래스의 계층 구조로, 교대하는 존재 양화자와 전칭 양화자를 사용하여 정의된다. PSPACE는 이 전체 다항식 계층을 포함하는 것으로 알려져 있다. 즉, PH의 모든 단계, 즉 0단계인 P부터 시작하여 1단계인 NP와 co-NP, 그리고 더 높은 단계들까지 모두 PSPACE의 부분집합이다.

이 관계는 PSPACE가 양화된 부울식(QBF) 문제를 포함한다는 점에서 이해할 수 있다. QBF는 임의의 수의 존재 및 전칭 양화자가 교대로 나타날 수 있는 논리식의 진위를 판단하는 문제로, 이는 PH의 정의와 유사한 구조를 가진다. 실제로, PH의 k번째 단계에 속하는 임의의 문제는 특정 형태의 QBF(양화자 깊이가 k로 고정된)로 표현될 수 있으며, 이 QBF는 PSPACE에 속하는 보다 일반적인 문제의 특수한 경우에 해당한다.

따라서 PSPACE와 PH의 관계는 다음과 같이 요약할 수 있다.

PSPACE가 PH를 진부분집합으로 포함하는지, 즉 PH가 PSPACE와 동일한지는 아직 해결되지 않은 중요한 열린 문제이다. 만약 PH = PSPACE라면, 다항식 계층이 특정 단계에서 붕괴된다는 강력한 결과를 함의하게 된다. 현재까지의 연구는 이 두 복잡도 클래스가 다를 가능성이 높다는 견해를 지지하지만, 엄밀한 증명은 이루어지지 않았다.

PSPACE와 EXPTIME의 관계는 복잡도 이론에서 중요한 포함 관계를 보여준다. 모든 PSPACE 문제는 EXPTIME 문제이기도 하다. 즉, PSPACE ⊆ EXPTIME이다. 이는 다항식 공간을 사용하는 알고리즘이 지수 시간을 초과하지 않는다는 사실에서 비롯된다. 다항식 공간을 사용할 수 있는 튜링 기계의 가능한 구성(configuration)의 총 개수는 지수적으로 제한되기 때문에, 이 기계가 같은 상태를 반복하지 않는다고 가정하면 그 실행 시간도 지수 시간을 넘지 않게 된다.

그러나 이 두 복잡도 클래스가 동일한지는 아직 알려지지 않았다. PSPACE ≠ EXPTIME일 것으로 널리 추측되지만, 이는 아직 증명되지 않은 열린 문제이다. 만약 두 클래스가 같다면, 이는 P ≠ PSPACE를 의미하게 되는데, 이는 P = EXPTIME이라는 강력한 결과를 함의하기 때문이다. P = EXPTIME은 대부분의 학자들이 믿지 않는 시나리오이므로, PSPACE가 EXPTIME의 진부분집합일 가능성이 매우 높다고 여겨진다.

이 관계는 다항식 시간 계층(PH)과의 관계와도 연결된다. PH는 PSPACE에 포함되며, 만약 PH = PSPACE라면 이 계층이 붕괴된다는 의미가 된다. 한편, PSPACE가 EXPTIME에 포함된다는 것은, 다항식 공간으로 풀 수 있는 모든 문제는 지수 시간 안에는 확실히 풀린다는 것을 보장한다. 그러나 그 역, 즉 모든 지수 시간 문제가 다항식 공간으로도 풀릴 것이라는 보장은 없다. 시간 계층 정리에 따르면 EXPTIME에는 PSPACE에 속하지 않는 문제, 즉 더 많은 공간을 필요로 하는 문제가 반드시 존재한다.

PSPACE-완전 문제의 가장 대표적인 예는 양화된 부울식(Quantified Boolean Formula, QBF 또는 TQBF) 문제이다. 이 문제는 명제 논리 식에 존재 양화사와 전칭 양화사가 모두 포함되어 있을 때, 그 식의 진릿값을 평가하는 것이다. 모든 변수가 존재 양화사나 전칭 양화사로 묶여 있는 식을 평가하는 문제는 PSPACE-완전임이 알려져 있으며, 이는 PSPACE의 완전성을 증명하는 데 핵심적인 역할을 한다.

게임 이론에서도 여러 PSPACE-완전 문제가 발견된다. 예를 들어, 지뢰찾기 게임의 일반화된 판정 문제, 혹은 체스나 오목과 같은 보드 게임을 임의의 크기의 보드로 일반화했을 때의 승패 판정 문제가 여기에 해당한다. 이러한 게임 문제들은 상대방의 모든 가능한 수에 대해 자신의 최선의 수를 재귀적으로 계산해야 하므로, 다항식 공간은 충분할 수 있지만 다항식 시간 내에 해결하기는 매우 어려운 경우가 많다.

다음은 몇 가지 주요 PSPACE-완전 문제를 정리한 표이다.

이 외에도 특정 형태의 자동 계획(Automated Planning) 문제나, 두 정규 표현식의 동치성 판정 문제 등 다양한 분야에서 PSPACE-완전인 문제들이 존재한다. 이러한 문제들은 이론적으로는 다항식 공간으로 해결 가능하지만, 실제로 효율적인 알고리즘을 찾는 것은 매우 어려운 것으로 알려져 있다.

PSPACE-완전성을 증명하는 일반적인 방법은 다항 시간 변환(Polynomial-time reduction)을 사용하는 것이다. 구체적으로, 어떤 문제 A가 PSPACE-완전임을 보이려면, 이미 알려진 PSPACE-완전 문제 B를 A로 다항 시간 내에 변환할 수 있음을 증명하면 된다. 이는 문제 A가 PSPACE에 속함(PSPACE-hard)과 PSPACE 안의 모든 문제가 A로 환원될 수 있음을 의미한다.

가장 핵심적이고 대표적인 PSPACE-완전 문제는 양화된 부울식(Quantified Boolean Formula, QBF) 또는 그 변형인 TQBF(True Quantified Boolean Formula) 문제이다. 따라서 대부분의 새로운 PSPACE-완전성 증명은 이 TQBF 문제로부터의 환원을 통해 이루어진다. 예를 들어, 특정 보드 게임의 일반화된 문제나 자동 계획(Automated Planning) 문제의 PSPACE-완전성을 증명할 때, 게임의 각 수나 계획의 각 단계를 TQBF의 양화사(Quantifier)와 변수 할당에 대응시켜 구성한다.

이러한 환원 과정에서 키가 되는 것은 공간의 효율적인 활용이다. 다항식 시간 변환이 가능해야 하지만, 핵심은 문제의 인스턴스를 다른 형태로 옮기는 과정에서 다항식 공간의 제약을 넘지 않으면서, 원래 문제의 계산 역사(computation history)나 전략 수립 과정을 새로운 문제의 구조에 담아낼 수 있어야 한다. 사빅치 정리에 의해 PSPACE와 NPSPACE가 동일하므로, 비결정적 선택을 포함한 계산 경로를 표현하는 데도 유리하다.