Fact-checked by Grok 2 weeks ago

PSPACE

In computational complexity theory, PSPACE is the class of decision problems that can be solved by a deterministic Turing machine using a polynomial amount of space, formally defined as the union over constants c > 0 of the space complexity classes \mathsf{SPACE}(n^c).^[1] This class encompasses all problems in P (polynomial-time solvable problems) and NP (nondeterministic polynomial-time solvable problems), since polynomial time implies polynomial space, establishing the inclusions \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE}.^[2] A fundamental result, Savitch's theorem, proves that the nondeterministic variant NPSPACE equals PSPACE, showing \mathsf{NPSPACE} \subseteq \mathsf{DSPACE}(n^2) and thus \mathsf{PSPACE} = \mathsf{NPSPACE}.^[3] Key properties of PSPACE include its position in the polynomial hierarchy, where the entire hierarchy \mathsf{PH} is contained within it (\mathsf{PH} \subseteq \mathsf{PSPACE}), though whether equality holds remains an open question.^[4] PSPACE-complete problems, which capture the hardest problems in the class under polynomial-time reductions, include the Quantified Boolean Formulas problem (TQBF), where one determines the truth value of a fully quantified Boolean formula, and formalizations of strategy games like chess or Go on an n \times n board, deciding if a given player has a winning strategy.^[5] These completeness results highlight PSPACE's relevance to interactive proofs, planning, and verification, with implications for unresolved questions like whether \mathsf{P} = \mathsf{NP} = \mathsf{PSPACE}.^[6]

Definition and Fundamentals

Formal Definition

The class PSPACE consists of all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of space. Formally, for a function f: \mathbb{N} \to \mathbb{N}, the space complexity class \mathsf{SPACE}(f(n)) is the set of languages L such that there exists a deterministic Turing machine M that decides L and, on every input of length n, uses at most O(f(n)) space on its work tapes (with the input tape being read-only and not counted toward the space bound).^[5] Then, \mathsf{PSPACE} = \bigcup_{k \geq 1} \mathsf{SPACE}(n^k).^[5] The nondeterministic analogue is defined similarly: \mathsf{NSPACE}(f(n)) is the set of languages L such that there exists a nondeterministic Turing machine M that decides L using at most O(f(n)) space on inputs of length n.^[5] Thus, \mathsf{NPSPACE} = \bigcup_{k \geq 1} \mathsf{NSPACE}(n^k).^[5] A language L is in \mathsf{PSPACE} if there exists a deterministic Turing machine M and a constant k such that, for all inputs x of length n, M decides whether x \in L using at most n^k space.^[5] Savitch's theorem establishes that nondeterminism provides no additional power for polynomial space: \mathsf{NPSPACE} = \mathsf{PSPACE}.^[7] Proved by Walter Savitch in 1970, the theorem more generally states that for any space-constructible function s(n) \geq \log n, \mathsf{NSPACE}(s(n)) \subseteq \mathsf{SPACE}(s(n)^2).^[7] The proof proceeds by showing that reachability in the configuration graph of the nondeterministic machine (from initial to accepting configurations) can be decided deterministically using quadratic space: recursively check, for each possible intermediate configuration C, whether there is a path of length at most s(n)^2 from the start to C and from C to an accepting configuration, leveraging the fact that the graph has $2^{O(s(n))} vertices.^[7] For polynomial s(n) = n^k, this simulation uses O((n^k)^2) = O(n^{2k}) space, which remains polynomial, yielding the equality.^[7] Since space-bounded deterministic Turing machines are closed under complementation—simply swap accepting and rejecting states—\mathsf{co\text{-}PSPACE} = \mathsf{PSPACE}.^[5]

Basic Properties

One of the fundamental properties of PSPACE is its self-duality, expressed as PSPACE = co-PSPACE, meaning the class is closed under complementation. This equality holds because PSPACE consists of languages decided by deterministic poly-space Turing machines, which are closed under complement by swapping accepting and rejecting states; by Savitch's theorem, PSPACE = NPSPACE, implying NPSPACE = co-NPSPACE.^[7] PSPACE is also closed under union and intersection. For union, if L_1 and L_2 are languages in PSPACE decided by deterministic Turing machines M_1 and M_2 using O(n^k) space for some constant k, then L_1 \cup L_2 can be decided by a machine that first simulates M_1 on the input and accepts if it does; otherwise, it simulates M_2 and accepts if that does. The simulations occur sequentially on the same space, reusing the work tape after each, so the total space remains O(n^k).^[8] Similarly, for intersection, the machine simulates both M_1 and M_2 sequentially and accepts only if both accept, again preserving the polynomial space bound.^[8] The class PSPACE is closed under polynomial-time many-one reductions. If L_1 \leq_p L_2 via a polynomial-time computable function f and L_2 \in PSPACE, then a machine for L_1 computes f(x) using at most polynomial space (since polynomial time implies polynomial space) and then simulates the PSPACE machine for L_2 on f(x), with the additive space usage still polynomial in |x|.^[9] The space hierarchy theorem implies strict inclusions within the space complexity classes leading to PSPACE, such as \mathsf{SPACE}(n) \subsetneq \mathsf{SPACE}(n \log n) \subsetneq \mathsf{PSPACE}. This separation arises because for space-constructible functions f(n) and g(n) where f(n) \log f(n) = o(g(n)), there exist languages decidable in \mathsf{SPACE}(g(n)) but not in \mathsf{SPACE}(f(n)), allowing the construction of languages that separate these polynomial-space subclasses from PSPACE.^[10]

Relationships to Other Classes

Inclusion Relations

The class PSPACE occupies a central position in the hierarchy of complexity classes, with well-established inclusion relations linking it to both lower and higher levels. Specifically, the inclusions form the chain L ⊆ NL ⊆ P ⊆ NP ⊆ PH ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE, where L denotes deterministic logspace, NL nondeterministic logspace, P polynomial time, NP nondeterministic polynomial time, PH the polynomial hierarchy, NPSPACE nondeterministic polynomial space, EXPTIME deterministic exponential time, NEXPTIME nondeterministic exponential time, and EXPSPACE exponential space.^[11] The inclusion P ⊆ PSPACE follows directly from the observation that any deterministic polynomial-time computation can be carried out using at most polynomial space, as the working tape is written sequentially and bounded by the running time.^[11] Similarly, NP ⊆ PSPACE holds because nondeterministic polynomial-time computations can be simulated deterministically in polynomial space via Savitch's theorem, which states that NSPACE(s(n)) ⊆ DSPACE(s(n)^2) for space bounds s(n) ≥ log n, implying NPSPACE ⊆ PSPACE and the trivial inclusion PSPACE ⊆ NPSPACE (as deterministic space is a special case of nondeterministic space), establishing that PSPACE = NPSPACE. The containment PH ⊆ PSPACE arises from the ability to simulate the alternating existential and universal quantifiers defining levels of the polynomial hierarchy using polynomial space, achieved through recursive elimination of quantifiers in a space-bounded manner that preserves the polynomial-time predicates at each level.^[12] Finally, the equality IP = PSPACE, established by Shamir, shows that interactive proof systems with polynomial-time verifiers capture exactly the power of polynomial space, as PSPACE computations can be simulated via interactive protocols using arithmetization techniques.^[13]

Known Separations

The space hierarchy theorem establishes that PSPACE is strictly contained in EXPSPACE, demonstrating that there exist problems solvable in exponential space but not in polynomial space. This separation follows from diagonalization arguments showing that increasing the space bound from polynomial to exponential allows for strictly more computational power. A similar hierarchy argument separates nondeterministic logspace (NL) from PSPACE. Savitch's theorem implies that NL is contained in deterministic space O(\log^2 n), and the space hierarchy theorem then yields a strict separation between DSPACE(\log^2 n) and DSPACE(n), with the latter contained in PSPACE. Padding techniques can also amplify this separation by embedding logspace computations into polynomial space bounds while preserving the hierarchy distinctions. Relativized separations provide further insight into the structure of PSPACE relative to other classes. There exist oracles A such that P^A = PSPACE^A and oracles B such that P^B \neq PSPACE^B, indicating that any non-relativizing proof technique is necessary to resolve the unrelativized question P ? PSPACE. The Baker–Gill–Solovay theorem constructs oracles relative to which P = NP and oracles relative to which P \neq NP, underscoring the limitations of relativizing techniques for broader separations involving PSPACE. The relationship between PSPACE and EXPTIME remains unresolved unconditionally, with no known separation or collapse. However, this question relativizes in both directions: there are oracles where PSPACE^A = [EXPTIME](/page/EXPTIME)^A and oracles where PSPACE^B \neq [EXPTIME](/page/EXPTIME)^B.^[14]

Structural Properties

Closure Properties

PSPACE exhibits several advanced closure properties that extend its basic behaviors under Boolean operations. Notably, it is closed under existential projection over polynomially many bits: if L \in PSPACE, then the language \{x \mid \exists y, |y| \leq |x|^{O(1)}, (x,y) \in L\} is also in PSPACE. This follows from the equivalence NPSPACE = PSPACE established by Savitch's theorem, as existential quantification corresponds to nondeterministic guessing within polynomial space. Similarly, closure under complement implies closure under universal projection: \{x \mid \forall y, |y| \leq |x|^{O(1)}, (x,y) \in L\}, which is the complement of the existential projection of the complement of L. These properties underpin the PSPACE-completeness of quantified Boolean formulas (QBF), where alternating existential and universal quantifiers over polynomial bits can be evaluated in polynomial space by recursive evaluation, reusing space for subformulas. PSPACE is also closed under polynomial-time many-one reductions and polynomial-time Turing reductions. For many-one reductions, if L \leq_m^p L' via a polynomial-time computable function f and L' \in PSPACE, then L \in PSPACE, as membership in L reduces to computing f(x) (in polynomial time, hence polynomial space) and checking f(x) \in L'. For Turing reductions, a polynomial-time machine with oracle access to L' \in PSPACE can be simulated directly, as the polynomial number of oracle queries can be handled sequentially, reusing the polynomial space for each query without accumulation. These closures preserve membership under standard reduction techniques in complexity theory. While PSPACE is closed under union and intersection (as noted in basic properties), its handling of disjoint union—such as \{0w \mid w \in L_1\} \cup \{1w \mid w \in L_2\} for L_1, L_2 \in PSPACE—avoids naive parallel simulation that might inflate space requirements. Instead, effective closure is achieved via nondeterminism: a machine nondeterministically guesses the prefix (0 or 1), strips it, and verifies membership in the corresponding language, leveraging NPSPACE = PSPACE to maintain polynomial space. Furthermore, PSPACE is closed under inverse homomorphisms, including those applied to regular languages. If L \in PSPACE and h: \Sigma^* \to \Delta^* is a homomorphism, then h^{-1}(L) = \{w \in \Sigma^* \mid h(w) \in L\} \in PSPACE, since h(w) can be computed in linear time and linear space (as |h(w)| = O(|w|)), followed by a polynomial-space check for membership in L. This holds particularly when L is regular, as the overall decision remains within polynomial space, mirroring closure behaviors in lower complexity classes like regular languages but scaled to PSPACE. These operational closures have implications for circuit complexity: PSPACE contains languages outside ACC^0, the class of constant-depth circuits with polynomial size and modulo gates, separating PSPACE from bounded-depth models.^[15]

Alternative Characterizations

One prominent alternative characterization of PSPACE arises from alternating Turing machines (ATMs), a model that extends nondeterministic Turing machines by incorporating alternating existential and universal quantification over computation branches. Specifically, PSPACE equals APTIME, the class of languages accepted by ATMs running in polynomial time.^[16] This equivalence holds because the polynomial-time bound on ATMs corresponds precisely to polynomial-space computation in standard Turing machines, as alternation allows efficient exploration of exponentially many configurations without exceeding polynomial space.^[16] Another characterization uses descriptive complexity theory, equating PSPACE to the class of properties expressible in second-order logic extended with a transitive-closure operator, denoted SO(TC), over finite unordered structures. Equivalently, on finite ordered structures (which include a linear order predicate), full second-order logic SO captures PSPACE, as the order enables encoding of polynomial-space computations via second-order quantifiers over relations. This logical view highlights PSPACE's robustness, linking it to fixed-point extensions of first-order logic like FO(PFP), where inflationary fixed points simulate space-bounded recursion. PSPACE can also be viewed through the lens of game theory, specifically as the class of languages where membership corresponds to the first player having a winning strategy in quantified Boolean formula (QBF) games. In such games, players alternately choose truth values for variables in a prenex-normal-form Boolean formula, with existential quantifiers representing moves by the existential player and universal quantifiers by the universal player; the existential player wins if the formula evaluates to true.^[16] This game-theoretic formulation directly mirrors the alternating quantification in ATMs and underscores PSPACE's connection to strategic decision problems in two-player perfect-information games.^[16] In terms of leaf languages, under polynomial-time many-one reductions, PSPACE consists of languages reducible to PSPACE-complete leaf languages, such as those defined by regular languages over balanced computation trees, providing a uniform framework for classes between P and PSPACE. The equivalence between PSPACE and APTIME can be sketched by showing how a polynomial-space Turing machine simulates an ATM via recursive verification of configurations. For an existential branch, the simulator nondeterministically guesses a successor configuration and recursively checks its acceptance; for a universal branch, it deterministically verifies that all possible successor configurations accept. This recursion depth is bounded by the polynomial time of the ATM, and each recursive call uses polynomial space to store the current configuration, ensuring the overall simulation stays within polynomial space—complementing Savitch's theorem that nondeterministic polynomial space equals deterministic polynomial space.^[16]

PSPACE-Completeness

Definition and Reductions

A language L is PSPACE-complete if it belongs to PSPACE and is PSPACE-hard, meaning that every language in PSPACE is polynomial-time many-one reducible to L.^[5] This definition mirrors the notion of NP-completeness but operates within the polynomial-space framework, where hardness is established via reductions that preserve membership while running in polynomial time.^[5] PSPACE-completeness is typically proven using a Cook-Levin-style theorem adapted for space-bounded computation, which reduces the acceptance problem of an arbitrary polynomial-space Turing machine to the true quantified Boolean formulas problem (TQBF) in polynomial time.^[5] This reduction encodes the machine's configuration graph into a quantified Boolean formula, where existential and universal quantifiers correspond to nondeterministic and deterministic choices, respectively, ensuring the formula is true if and only if the machine accepts.^[17] The standard reductions for PSPACE-completeness are polynomial-time many-one reductions, though the class remains complete under stricter log-space reductions, which compute the reduction function using only logarithmic space.^[5] Nondeterministic reductions are also considered in some contexts, but log-space reductions provide the strongest evidence of hardness due to their resource limitations.^[18] The first PSPACE-complete problem, TQBF, was identified by Albert R. Meyer and Larry J. Stockmeyer in 1972, generalizing Cook's earlier work on NP-completeness.^[5]^[19] If any PSPACE-complete problem belongs to P, then P = PSPACE, as polynomial-time reductions would imply that all of PSPACE collapses to P.^[5]

Canonical Complete Problems

The canonical PSPACE-complete problem is the true quantified Boolean formula problem (TQBF), consisting of fully quantified Boolean formulas in prenex normal form over propositional variables, where the quantifiers alternate starting with an existential quantifier and the quantifier-free matrix is in 3-CNF. TQBF is PSPACE-complete under log-space reductions, as established in the seminal work defining the polynomial-time hierarchy.^[5] To show membership in PSPACE, a recursive algorithm evaluates the formula by iteratively instantiating variables according to their quantifiers: for an existential quantifier ∃x φ, it checks if there exists a value for x making φ true; for a universal quantifier ∀x φ, it verifies φ for both values of x. This recursion depth is linear in the number of variables (polynomial in input size), and each level stores only the current variable assignment and partial evaluation, using O(n) space overall. Hardness follows from a log-space reduction from the acceptance problem of deterministic Turing machines using polynomial space: the computation is encoded as a quantified formula asserting the existence of an accepting configuration sequence, with variables representing tape contents, head positions, and states at each time step, ensuring the formula is true if and only if the machine accepts.^[5] Even when restricted to formulas requiring only linear space for evaluation—such as those with a linear number of variables and clauses—TQBF remains PSPACE-complete, demonstrating the tightness of the space bound for this problem. Variants include fully quantified 3-CNF formulas, which are also PSPACE-complete under log-space reductions via simple negation of literals to convert between CNF and DNF. Another variant is succinct circuit evaluation, where the Boolean formula is generated by a succinct circuit (itself described by a polynomial-size circuit producing the truth table or clauses), preserving PSPACE-completeness when the generated formula remains of polynomial size relative to the succinct description.^[5] TQBF solvers, which implement variants of the recursive evaluation with optimizations like clause learning and dependency schemes, find applications in AI planning—where planning as satisfiability reduces to quantified formulas over actions and states—and in formal verification, such as checking safety properties in hardware designs modeled as alternating reachability games.^[20]

Examples from Logic and Games

One prominent example of a PSPACE-complete problem arising from logic is the formula game, a two-player game played on a fully quantified Boolean formula in prenex normal form, where existential quantifiers correspond to moves by the existential player (Evaluator) and universal quantifiers to moves by the universal player (Adversary). The players alternate assigning truth values to the variables in the order specified by the quantifiers, and the Evaluator wins if the resulting assignment satisfies the formula, while the Adversary wins otherwise; determining whether the Evaluator has a winning strategy from the initial position is PSPACE-complete, as it directly corresponds to evaluating the truth of the quantified Boolean formula (TQBF). In the realm of impartial graph games, generalized geography (also known as vertex geography) is a two-player game on a directed graph where players alternate selecting an unused vertex adjacent to the previous one, removing the selected vertex and its outgoing edges after each move, with the player unable to move losing; the problem of determining the winner with perfect play is PSPACE-complete via reduction from TQBF.^[21] Similarly, node Kayles is played on an undirected graph, where players alternate selecting a vertex and removing it along with its adjacent vertices, aiming to make the last valid move; deciding the winner under optimal play is also PSPACE-complete. Connection-based board games provide another intuitive class of PSPACE-complete problems. In Hex, played on an n × n hexagonal grid, two players alternate claiming edges of opposite colors to connect their respective sides, and determining which player has a winning strategy with perfect play is PSPACE-complete, even on planar bipartite graphs.^[22] This hardness extends to other connection games like Bridg-it and Y, where the goal is to form a path between designated boundaries, showing that winner determination remains PSPACE-complete. Puzzles modeled by nondeterministic constraint logic (NCL) capture the complexity of many sliding and reconfiguration problems, such as Rush Hour or Sokoban. In NCL, the game is played on a directed graph with weighted edges representing "tokens," where a move reverses an edge's direction provided it satisfies local inflow constraints at each vertex; deciding reachability of a target configuration from an initial one is PSPACE-complete under local reductions, enabling proofs of hardness for puzzles involving movable obstacles and goals. A broad class of traditional board games generalized to n × n boards, including checkers (under reasonable draw rules) and chess, are PSPACE-complete for determining the winner with perfect play, as established through reductions simulating quantified Boolean evaluations on the board state space.

Open Problems and Extensions

Major Unsolved Questions

One of the most prominent open questions in computational complexity theory is whether P = NP = PSPACE, with the prevailing belief among researchers that these classes are distinct hierarchies: P \subsetneq NP \subsetneq PSPACE. This separation has profound implications for verification, optimization, and planning problems, as PSPACE encompasses tasks requiring polynomial space but potentially exponential time, such as evaluating quantified Boolean formulas, while NP focuses on efficient verification. Resolving P = NP in the negative would confirm NP \neq P but leave open whether NP = PSPACE; conversely, proving P = PSPACE would collapse NP into P, resolving the Millennium Prize Problem for P versus NP.^[23]^[24] A related unresolved issue concerns the polynomial hierarchy (PH) and its containment within PSPACE. It is known that PH \subseteq PSPACE, but whether this inclusion is proper remains open, with equality implying a collapse of the hierarchy to PSPACE.^[25] Specifically, if NP = coNP, the hierarchy would collapse to the second level (\Delta_2^P), but broader collapses could align PH with PSPACE if alternating quantifiers beyond a fixed number prove unnecessary for PSPACE-complete problems. This connection arises because the PSPACE-complete problem TQBF (true quantified Boolean formulas) requires unbounded alternations, and placing it within a finite level of PH would force the entire hierarchy to collapse.^[26] Derandomization questions also intersect with PSPACE, particularly regarding whether probabilistic polynomial-time algorithms (BPP) can be efficiently simulated within deterministic space-bounded classes. It is established that BPP \subseteq PSPACE via brute-force enumeration of random strings, which uses polynomial space to compute acceptance probabilities exactly.^[27] However, whether PSPACE admits efficient deterministic algorithms relative to certain oracles—such as those separating randomness from space complexity—remains unresolved, as relativizing techniques show barriers to proving stronger derandomizations without non-relativizing methods.^[28] Space-time tradeoffs for canonical PSPACE-complete problems like TQBF further highlight unresolved complexities. TQBF can be solved in exponential time and polynomial space using recursive evaluation of quantifiers, but whether it admits a subexponential-time algorithm (say, 2^{o(n)}) is unknown and would imply PSPACE \subseteq subexponential time, a major breakthrough believed unlikely. In 2025, Ryan Williams proved that any algorithm running in time t can be simulated using space O(√t · polylog t), providing the first significant improvement on space-time simulation since the 1970s and facilitating progress toward separating P from PSPACE.^[29]^[30] Such improvements are tied to the broader P versus PSPACE question, as any subexponential algorithm for TQBF would challenge the expected exponential-time requirement for PSPACE.^[31] The Millennium Prize Problem for P versus NP, established by the Clay Mathematics Institute in 2000, indirectly underscores these PSPACE-related questions, as a proof of P = NP would necessitate examining whether the resulting class equals PSPACE, potentially advancing understanding of space-bounded computation. Despite decades of effort, no progress has separated NP from PSPACE beyond inclusions, leaving these as foundational barriers in the field.^[32]

Connections to Quantum and Interactive Computing

One of the landmark results connecting PSPACE to interactive computing is the equality between the class of languages with interactive proofs (IP) and PSPACE, established by showing that public-coin interactive protocols with polynomial rounds can simulate polynomial-space computations.^[13] This theorem demonstrates that randomization and interaction allow a probabilistic verifier to check PSPACE computations efficiently, using techniques like arithmetization and sum-check protocols to reduce space-bounded verification to interactive challenges.^[13] Extending this to quantum settings, the class of quantum interactive proofs (QIP) also equals PSPACE, where the prover sends quantum messages to a quantum verifier.^[33] The proof relies on approximating semidefinite programs in polynomial space, which bounds the verification of quantum proofs by reducing them to classical space-efficient optimizations, thus confirming QIP's containment in PSPACE while leveraging the known IP = PSPACE result.^[33] This equality underscores PSPACE's invariance under quantum enhancements in interactive models. Further ties to quantum computing arise through models inspired by quantum gravity, such as closed timelike curves (CTCs), where PSPACE equals both the classical power with CTC oracles (P^CTC) and the bounded-error quantum polynomial-time power with CTCs (BQP^CTC).^[34] In this framework, CTCs enable fixed-point computations that simulate space-bounded Turing machines without increasing beyond polynomial resources, collapsing classical and quantum hierarchies relative to such oracles.^[34] Recent advancements highlight separations in relativized settings, such as oracle results from quantum query complexity showing BQP not equal to PSPACE, reinforcing that quantum speedups do not collapse the polynomial hierarchy up to PSPACE.^[35] Additionally, the inclusion AM ⊆ IP, where AM denotes two-message public-coin protocols, implies that derandomizing Arthur-Merlin protocols could yield non-interactive proofs for PSPACE via transformations, with ongoing work exploring efficient derandomization paths. These equalities and separations illustrate PSPACE's central role as a robust boundary across interactive, quantum, and hypothetical physical models of computation.

References

[1]
[PDF] Lecture 6 1 Space Complexity - UMD Computer Science
1 Space Complexity. We define some of the important space-complexity classes we will study: Definition 1. PSPACE def. = J c space(nc). NPSPACE def. = J c nspace ...
[2]
[PDF] 9. PSPACE - cs.Princeton
Jul 25, 2017 · PSPACE. Decision problems solvable in polynomial space. Observation. P ⊆ PSPACE. 4 poly-time algorithm.
[3]
[PDF] Lecture 5: The Landscape of Complexity Classes
Jul 21, 2000 · The equality PSPACE = NPSPACE is a consequence of Savitch's Theorem and the inclusion NL ⊆ P can also be obtained by that same idea of reducing ...<|control11|><|separator|>
[4]
[PDF] Complexity Classes - Texas A&M University
Definition. The class of all decision problems that can be solved using a polynomial amount of space. Proposition. PH Ď PSPACE. 19 / 41. Page 24. Randomized ...
[5]
[PDF] Computational Complexity: A Modern Approach - Princeton University
Jan 8, 2007 · Since complete problems can help capture the essence of a complexity class, we now present some complete problems for PSPACE. Definition 4.8.
[6]
[PDF] Lecture 20: PSPACE-Complete problems, Complexity as Games
For formalizations of many popular two-player games, it is PSPACE-complete to decide which player has a winning strategy on a game board! Complexity Theory as ...
[7]
[PDF] Lecture 18: Complexity Classes 1 Introduction
Mar 25, 2024 · The definition given in your algorithms course is that NP is the class of languages verifiable ... NP ⊆ PSPACE, since SAT ∈ SPACE(n).
[8]
Relationships between nondeterministic and deterministic tape ...
The amount of storage needed to simulate a nondeterministic tape bounded Turingmachine on a deterministic Turing machine is investigated.
[9]
[PDF] Tutorial 9 Space Complexity - CSE IIT KGP
1. Show that. (a) PSPACE is closed under union, intersection, complement and Kleene Closure. Solution: Let L1,L2 ...
[10]
[PDF] 1 Polynomial-Time Mapping Reductions - Search StFX.ca
The classes P, NP, PSPACE, and EXP are closed under polynomial-time mapping reductions. Proof. We will prove closure for the class NP; proofs for the other ...
[11]
[PDF] Hierarchies of Memory Limited Computations
Hierarchies of Memory Limited Computations. Conference Paper · November 1965. DOI: 10.1109/FOCS.1965.11 · Source: IEEE Xplore. CITATIONS. 273. READS. 209. 3 ...
[12]
[PDF] Complexity Classes - Brown CS
Complete problems are defined and the P-complete,. NP-complete, and PSPACE-complete problems are examined. We then turn to the PRAM and circuit models and ...
[13]
[PDF] Lecture 8 1 The Polynomial Hierarchy
Since PSPACE has complete languages, this indicates that PH is strictly contained in PSPACE. The polynomial hierarchy can also be defined using alternating ...
[14]
IP = PSPACE | Journal of the ACM
In this paper, it is proven that when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those ...
[15]
Relativizations of the P = ? NP Question - SIAM Publications Library
We investigate relativized versions of the open question of whether every language accepted nondeterministically in polynomial time can be recognized ...
[16]
[PDF] The Role of Relativization in Complexity Theory 1 Introduction
Perhaps we can use this characterization to separate NP from higher complexity classes like PSPACE and EXP by separating PCP(logn;1) from these classes.
[17]
Alternation | Journal of the ACM
We define alternating Turing Machines which are like nondeterministic Turing Machines, except that existential and universal quantifiers alternate.Missing: APTIME | Show results with:APTIME
[18]
[PDF] TQBF is PSPACE-complete - Zoo | Yale University
The techniques developed in the proof of the Cook-Levin Theorem can be used straightforwardly to show that there is such a formula and that, moreover, it can ...Missing: style | Show results with:style
[19]
[PDF] PSPACE-Completeness of TQBF, Logspace Computation
As usual, we'll use reductions to help us study this question, but poly-time reductions are now too coarse-grained. Definition 3 (Logspace Reductions). A ...
[20]
[PDF] The Equivalence Problem for Regular Expressions with Squaring ...
In the second part of the paper we describe and give some simple properties of a. "hierarchy" of languages. Each succeeding class of the hierarchy is obtained ...Missing: TQBF title
[21]
[PDF] Analysis of Search Based Algorithms for Satisfiability of Quantified ...
Many problems in AI planning [1] and sequential circuit verification [2] [3] can be formulated as QBF instances.Missing: citation | Show results with:citation
[22]
GO Is Polynomial-Space Hard | Journal of the ACM
It is proved that GO is Pspace hard by reducing a Pspace-complete set, TQBF, to a game called generalized geography, then to a planar version of that game, and ...<|separator|>
[23]
Hex ist PSPACE-vollständig - SpringerLink
In this paper we will show that the same holds for the game of Hex. The crucial point of the proof is to establish PSPACE-hardness for a generalization of Hex ...
[24]
[PDF] The P versus NP problem - Clay Mathematics Institute
Statement of the Problem. The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is ...
[25]
P vs. PSPACE - Open Problem Garden
Apr 4, 2009 · Problem Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More ...Missing: survey | Show results with:survey
[26]
[PDF] Lecture 5: Polynomial Hierarchy - Cornell: Computer Science
Feb 3, 2009 · Note also that if PH = PSPACE, then the polynomial hierarchy collapses, since the complete language TQBF would fall in Σi for some i.
[27]
[PDF] Beyond NP: The Work and Legacy of Larry Stockmeyer
May 24, 2005 · Stockmeyer and Meyer [61, 58] gave a PSPACE- complete problem Bω (now TQBF) by generalizing the com- plete sets developed by Meyer and ...
[28]
[PDF] Lecture 12: Randomness Continued 1 Model - cs.wisc.edu
Feb 25, 2010 · The result that BPP ⊆ PSPACE follows from the fact that we can compute the probability of acceptance by a randomized machine, by exhaustively ...
[29]
[PDF] Derandomization: A Brief Overview - School of Computing Science
Jan 17, 2002 · BPP = P: once superpolynomial circuit lower bounds are proved for some language in EXP, the derandomization of BPP will follow. However ...
[30]
[PDF] 1 TQBF - Harvard SEAS
Feb 10, 2010 · Since TQBF is PSPACE complete, L reduces to TQBF in logspace, so if TQBF ∈ SPACE(n ), then L ∈ SPACE((nc) + log(n)). If < 1/c, we have a ...Missing: style | Show results with:style
[31]
http://theory.cs.princeton.edu/complexity/spacechap.pdf
[32]
[PDF] Worlds to Die Harder For - Lance Fortnow
Aug 11, 2021 · Pushing these limits further are good open problems. 4.1 P = PSPACE. Discovered by Baker, Gill and Solovay in the original oracle paper [BGS75].
[33]
[0907.4737] QIP = PSPACE - arXiv
Jul 27, 2009 · We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE.Missing: Kindler Kitaev Vidick 2011
[34]
[PDF] Closed Timelike Curves Make Quantum and Classical Computing ...
He also sketched a proof that PSPACE = PCTC ⊆ BQPCTC ⊆ EXP. That is, classical computers with polynomial-size CTCs have exactly the power of polynomial space,.Missing: Wigderson 2009
[35]
Oracle Separation of BQP and PH | Journal of the ACM
In this article, we show that in the black-box model (also known as query-complexity or decision-tree complexity), the answer is negative.