Understanding PSPACE: Definition and Significance

1. Defining PSPACE

Just as P is the class of problems solvable in polynomial time, PSPACE is the class of problems solvable in polynomial space.

Let's start with a formal definition.

To summarize the key definitions from the reading:

• PSPACE: This is the class of languages decidable by a deterministic Turing machine in polynomial space. Formally, $$\text{PSPACE}=\bigcup _{k\ge 0}\text{SPACE}(n^k)$$
• NPSPACE: This is the class of languages decidable by a nondeterministic Turing machine in polynomial space. Formally, $$\text{NPSPACE}=\bigcup _{k\ge 0}\text{NSPACE}(n^k)$$

A problem is in PSPACE if there exists an algorithm that solves it using memory that grows as a polynomial function of the input size (e.g., $O(n)$, $O(n^2)$, etc.). Crucially, there is no restriction on the running time. As we saw in the last lesson, a polynomial-space algorithm might run for exponential time.

2. PSPACE in the Complexity Hierarchy

Where does PSPACE fit with P and NP? Let's watch a video that outlines the relationships.

Let's break down these crucial inclusions.

P ⊆ PSPACE

This follows directly from the fact that TIME(f(n)) ⊆ SPACE(f(n)). If a problem is in P, it can be solved by a deterministic TM in $O(n^k)$ time. In $t$ steps, a TM can visit at most $t$ cells. Therefore, this TM uses at most $O(n^k)$ space. Since it's solvable in polynomial time, it's also solvable in polynomial space.

NP ⊆ PSPACE

This is a more profound result. The video shows two ways to think about it.

Argument 1: Solving SAT in Polynomial Space

1. SAT is NP-complete: If we can solve SAT in polynomial space, we can solve any problem in NP in polynomial space. This is because any problem in NP can be reduced to SAT in polynomial time, which is also polynomial space.
2. The "Odometer" Algorithm: To check if a formula $\varphi$ with $m$ variables is satisfiable, we can deterministically iterate through all $2^m$ truth assignments.
   • We need space to store one assignment (e.g., a binary string of length $m$). This takes $O(m)$ space.
   • For each assignment, we evaluate $\varphi$, which takes polynomial time and thus polynomial space.
   • Crucially, we can reuse the same space for each new assignment. After checking 00...0, we reuse the space to check 00...1, and so on.
3. Result: The algorithm takes exponential time ($O(2^m\cdot \text{poly}(m))$) but only polynomial space ($O(m)+\text{poly}(m))$). Therefore, SAT is in PSPACE.

Your experience with building systems gives you an intuitive grasp of this time-space tradeoff. You can often reduce memory usage at the cost of more computation, for instance, by re-calculating values instead of storing them in a large cache. This algorithm is an extreme example of that principle.

Argument 2: The Generic Verifier Approach

A more abstract way to see this, explained well in the video resource LINK, is to use the verifier definition of NP. A language is in NP if a "yes" instance has a polynomial-length certificate that can be checked by a polynomial-time verifier.

A deterministic PSPACE machine can simply:

1. Iterate through every possible certificate string of the required polynomial length.
2. For each certificate, run the polynomial-time verifier.
3. If the verifier accepts, halt and accept. If all certificates are tried and none work, reject.

Again, space is reused for each certificate, so the total space is polynomial (enough for one certificate and one run of the verifier).

This gives us the hierarchy: P ⊆ NP ⊆ PSPACE.

3. A Quintessential PSPACE Problem: TQBF

While SAT is in PSPACE, it's not thought to be "PSPACE-hard" — it's too easy. The canonical problem that captures the full difficulty of PSPACE is TQBF (True Quantified Boolean Formulas).

A Quantified Boolean Formula (QBF) extends a regular boolean formula with universal ($\forall$, "for all") and existential ($\exists$, "there exists") quantifiers. For example:

This formula reads: "For all possible truth values of $x$, does there exist a truth value of $y$ such that the expression is true?"

The TQBF problem asks: given a QBF with no free variables, is it true?

Let's watch how to solve TQBF in polynomial space.

The algorithm presented in the video is a beautiful illustration of space reusability. Let's call it SOLVE(\phi):

• Base Case: If $\varphi$ has no quantifiers, evaluate it directly.
• Recursive Step ($\exists x:\psi$): Recursively call SOLVE(\psi) with $x=\text{true}$ and SOLVE(\psi) with $x=\text{false}$. Return true if either call returns true.
• Recursive Step ($\forall x:\psi$): Recursively call SOLVE(\psi) with $x=\text{true}$ and SOLVE(\psi) with $x=\text{false}$. Return true if both calls return true.

The key to the space analysis is that the two recursive calls in each step can be executed sequentially. After computing the result for $x=\text{true}$, we can discard all the memory used for that branch (except the boolean result) and reuse it for the $x=\text{false}$ branch.

This is exactly how a call stack works in most programming languages. The space needed is proportional to the maximum depth of the recursion, which is the number of variables in the formula. If the input formula has length $n$, it can have at most $O(n)$ variables. Therefore, the algorithm runs in $O(n)$ space, placing TQBF firmly in PSPACE.

4. A Surprising Equivalence: PSPACE = NPSPACE

One of the most remarkable results in complexity theory concerns the power of nondeterminism in space-bounded computation. While it is widely believed that P ≠ NP, we know for a fact that PSPACE = NPSPACE.

This result is known as Savitch's Theorem. It states that any problem solvable by a nondeterministic TM using $s(n)$ space can be solved by a deterministic TM using $O(s(n{)}^2)$ space.

For polynomial space, this means:
If a problem is in NPSPACE, it's solvable in $O(n^k)$ space by an NTM. By Savitch's Theorem, it's solvable in $O((n^k{)}^2)=O(n^{2k})$ space by a DTM. Since $n^{2k}$ is still a polynomial, the problem is also in PSPACE.

Therefore, NPSPACE ⊆ PSPACE. Since we already know PSPACE ⊆ NPSPACE (a deterministic TM is a special case of an NTM), the two classes must be equal.

The proof of Savitch's theorem uses a clever recursive, divide-and-conquer strategy similar in spirit to the TQBF solver, checking for reachability between configurations. The MIT lecture's ladder problem (covered in sections 6 and 7 of LINK) is designed as an introductory example of this very technique.

Conclusion

This lesson completes our tour of the foundational complexity classes. By defining PSPACE, we have characterized a vast and important class of problems that are considered solvable in principle, even if they require an infeasible amount of time.

Key Takeaways:

• PSPACE is the class of decision problems solvable by a deterministic Turing machine using a polynomial amount of tape space.
• The known hierarchy is P ⊆ NP ⊆ PSPACE. The inclusions are believed to be proper, but this has not been proven.
• The reusability of space allows exponential-time algorithms to run in polynomial space, which is why NP ⊆ PSPACE.
• TQBF is a canonical PSPACE-complete problem, solvable with a recursive algorithm that uses linear space.
• A cornerstone result, Savitch's Theorem, proves that PSPACE = NPSPACE, a stark contrast to the presumed P vs. NP separation.

This concludes our course on the Theory of Computation. You have journeyed from the simplest models of computation, like finite automata, through the expressive power of grammars and pushdown automata, to the universal model of the Turing machine. Finally, you have explored the limits of computation itself, classifying problems by their inherent difficulty into the major complexity classes P, NP, and PSPACE. This theoretical framework is the bedrock upon which the entire field of computer science is built. Congratulations on completing this journey