ARTIKELDIGITAL.COM

{\mathsf {P{\overset {?}{=}}PSPACE}}} ⁠ More unsolved problems in computer science In computational complexity theory, PSPACE is the set of all decision...

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input...

problems solvable by an interactive proof system. It is equal to the class PSPACE. The result was established in a series of papers: the first by Lund, Karloff...

is contained in PSPACE, which also proves that QIP = IP = PSPACE, since PSPACE is easily shown to be in QIP using the result IP = PSPACE. Watrous, John...

the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing...

than PSPACE, the class of problems decidable in polynomial space. PSPACE is equivalent to NPSPACE by Savitch's theorem. Again, whether P = PSPACE is an...

PSPACE {\displaystyle {\textsf {P}}\subseteq {\textsf {NP}}\subseteq {\textsf {PP}}\subseteq {\textsf {PSPACE}}} , but it is possible that P = PSPACE...

complexity classes relate to each other in the following way: L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME⊆EXPSPACE Where ⊆ denotes the subset relation. However,...

prove that IP = PSPACE. However, in 2008, Scott Aaronson and Avi Wigderson showed that the main technical tool used in the IP = PSPACE proof, known as...

interactive proofs, and the quantum analogue of the celebrated result IP = PSPACE: QIP = PSPACE. This was preceded by a series of results, showing QIP can be constrained...

basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Furthermore, by the time hierarchy theorem...

the drawing rule in standard Checkers), then the problem is in PSPACE, thus it is PSPACE-complete. However, without this bound, Checkers is EXPTIME-complete...

complexity. Without ko, Go is PSPACE-hard. This is proved by reducing True Quantified Boolean Formula, which is known to be PSPACE-complete, to generalized...

removing all tiles is PSPACE-complete, and the game is NP-complete if looking below tiles is allowed. It has been proven that it is PSPACE-hard to approximate...

are strict subsets, since we don't even know if P is a strict subset of PSPACE. BPP is contained in the second level of the polynomial hierarchy and therefore...

PP\subseteq PSPACE\subseteq EXP}}} As the problem of ⁠ P   = ?   P S P A C E {\displaystyle {\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}} ⁠ has...

work was hardly two weeks old when Adi Shamir employed it to prove that IP=PSPACE. Quickly following up on this (January 17, 1990, less than two months after...

Second-order logic with a transitive closure operator (commutative or not) yields PSPACE, the problems solvable in polynomial space. Second-order logic with a least...

mathematics List of undecidable problems List of NP-complete problems List of PSPACE-complete problems List of problems in loop theory and quasigroup theory...

ignoring the proof and solving it. NP is contained in PSPACE—to show this, it suffices to construct a PSPACE machine that loops over all proof strings and feeds...

Here are some of the more commonly known problems that are PSPACE-complete when expressed as decision problems. This list is in no way comprehensive. Generalized...

1145/321978.321989. S2CID 8845949. Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Informatica. 15 (2): 167–191. doi:10.1007/bf00288964...

⁠ is symmetrical. co-NP is a subset of PH, which itself is a subset of PSPACE. An example of a problem that is known to belong to both NP and co-NP (but...

complicates the analysis considerably. Playing Dots and Boxes optimally is PSPACE-complete. Dots and Boxes need not be played on a rectangular grid – it can...

is in EXPSPACE, and is PSPACE-hard. It's proved to be PSPACE-hard by reducing Generalized Geography, a problem known to be PSPACE-hard, to a game of Ghost...

need not store game states; however many games of interest are known to be PSPACE-hard, and it follows that their space complexity will be lower-bounded by...

in PSPACE. It is unknown if any of these inclusions is unconditionally strict, as it is not even known whether P is strictly contained in PSPACE or P...

computational complexity theory, generalized geography is a well-known PSPACE-complete problem. Geography is a children's game, where players take turns...

exponential time, a very large class. NEXPTIME contains PSPACE, and is believed to strictly contain PSPACE. Adding a constant number of additional provers beyond...

polynomial space, but not in non-deterministic polynomial time (unless NP = PSPACE). NP-hard problems do not have to be elements of the complexity class NP...

solution among the exponentially many branches. Probabilistic Turing machine PSPACE Garey, Michael R.; David S. Johnson (1979). Computers and Intractability:...

solution is PSPACE-complete. This is proved by reducing a graph game called nondeterministic constraint logic, which is known to be PSPACE-complete, to...

determining if the first player has a winning move in a given position is PSPACE-complete. The World Othello Championship (WOC), which started in 1977, was...

P, NP, and PSPACE is not known. However, it is known that P ⊆ B Q P ⊆ P S P A C E {\displaystyle {\mathsf {P\subseteq BQP\subseteq PSPACE}}} ; that is...

\exists z\ ((x\lor z)\land y)} QBF is the canonical complete problem for PSPACE, the class of problems solvable by a deterministic or nondeterministic Turing...

win for the first player in a given position is PSPACE-complete. Generalized hex and reversi are PSPACE-complete. For many generalized games which may...

capture mathematics associated with various complexity classes like P and PSPACE. Buss's work can be considered the continuation of Edward Nelson's work...

use O ( f ( n ) ) {\displaystyle O(f(n))} space. The complexity classes PSPACE and NPSPACE allow f {\displaystyle f} to be any polynomial, analogously...

in co-RP in DLOGCFL +,× P-complete in DLOGCFL ∪,∩,−,+ PSPACE-complete PSPACE-complete ∪,∩,+ PSPACE-complete NP-complete ∪,+ NP-complete NP-complete ∩,+...

are uniform (generated by a polynomial-time algorithm). PP is included in PSPACE. This can be easily shown by exhibiting a polynomial-space algorithm for...

complexity can be higher; in particular, testing reachability for Sokoban is PSPACE-complete. Rotation distance in binary trees and related problems of flip...

Lance Fortnow, Howard Karloff, and Noam Nisan, that the complexity classes PSPACE and IP are equal. 1983 – Erdős Prize of the Israel Mathematical Society...

classes relate to classical complexity classes such as P, NP, BPP, and PSPACE. One of the reasons quantum complexity theory is studied are the implications...

intersection problem or the non-emptiness of intersection problem, is a PSPACE-complete decision problem from the field of automata theory. The problem...

3233/ICG-2001-24104. S2CID 207577292. Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gomoku is PSPACE-complete)". Acta Informatica. 13: 59–66. doi:10.1007/bf00288536...

of as the hardest problems in EXPSPACE. EXPSPACE is a strict superset of PSPACE, NP, and P. It contains EXPTIME and is believed to strictly contain it,...

computational problem that is known to be NP-hard and in PSPACE, but is not known to be complete for NP, PSPACE, or any language in the polynomial hierarchy. ∃...

LOGCFL +,× P-hard, in co-NP L-hard, in LOGCFL ∪,∩,−,+ PSPACE-complete PSPACE-complete ∪,∩,+ PSPACE-complete NP-complete ∪,+ NP-complete NP-complete ∩,+...

cannot easily be proven, since this would prove that P is different from PSPACE. Simon's problem considers access to a function f : { 0 , 1 } n → { 0 ,...

configuration) is PSPACE-complete. This can be proved in two ways. The first way is by reducing a generalized Hex position, which is known to be PSPACE-complete...

NC = P problem NP = co-NP problem P = BPP problem P = PSPACE problem L = NL problem PH = PSPACE problem L = P problem L = RL problem Unique games conjecture...

airframe and powerplant ratings AP, an alternative characterization of PSPACE In computational complexity theory Application Processor, usually means...

minimization is PSPACE-complete. No efficient (polynomial time) algorithms are known, and under the standard assumption that P ≠ PSPACE, none exist. The...

proven to be PSPACE-complete. These hardness results form the basis for proofs that various games and puzzles are PSPACE-hard or PSPACE-complete. In the...

structures, a property is expressible in FO(PFP,X) if and only if it lies in PSPACE. Since the iterated predicates involved in calculating the partial fixed...

furthermore, NP ⊆ P/poly implies AM = MA If PSPACE ⊆ P/poly then P S P A C E = Σ 2 P ∩ Π 2 P {\displaystyle {\mathsf {PSPACE}}=\Sigma _{2}^{\mathsf {P}}\cap \Pi...

other probabilistic complexity classes (RP, co-RP, BPP, BQP, PP), which generalise P within PSPACE. It is unknown if any of these containments are strict....

unbreakable encryption, there are zero-knowledge proofs for all problems in IP = PSPACE, or in other words, anything that can be proven by an interactive proof...

non-deterministic) finite-state machines can reach a deadlock. This problem is PSPACE-complete, i.e., it is decidable, but not likely that there is an efficient...

ISBN 978-3-540-64310-4. Yang, Ke (2001). "Integer Circuit Evaluation Is PSPACE-Complete". Journal of Computer and System Sciences. 63 (2, September 2001):...

proved that this game is PSPACE-complete, which illustrates the observation that NP-complete puzzles tend to lead to PSPACE-complete games. Devil's Dice...

semialgebraic set is non-empty. This decision problem is NP-hard and lies in PSPACE, giving it significantly lower complexity than Alfred Tarski's quantifier...

Boolean formula problem (QBF), which can be shown to be PSPACE-complete. It is widely believed that PSPACE-complete problems are strictly harder than any problem...

formulas. PH is the set of languages definable by second-order formulas. PSPACE is the set of languages definable by second-order formulas with an added...

board. During this competition the pie rule is used. Solving Havannah is PSPACE-complete with respect to the size of the input graph. The proof is by a...

player eventually cannot perform a capture. Bob Hearn proved that Kōnane is PSPACE-complete with respect to the dimensions of the board, by a reduction from...

computing its output is PSPACE-complete. In 2015, this was strengthened to show that computing the output of Dantzig's pivot rule is PSPACE-complete. Analyzing...

probabilistic complexity classes (ZPP, co-RP, BPP, BQP, PP), which generalise P within PSPACE. It is unknown if any of these containments are strict....

that the problem of finding a PNE reachable from a given input state is PSPACE-complete. The class of ordinal potential games is even larger than the class...

context-sensitive grammar G, is PSPACE-complete. Moreover, there are context-sensitive grammars whose languages are PSPACE-complete. In other words, there...

player can achieve this, the game is a draw. TwixT has been proven to be PSPACE-complete for determining the game value, via a reduction from Hex. TwixT...

Foundations of Computer Science characterizing complexity classes such as PSPACE and NEXPTIME in terms of interactive proof systems; this work became part...

equivalence problem (do two input AFAs recognize the same language) are PSPACE-complete for AFAs. Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry...

already for a singleton alphabet. For larger alphabets, that problem is PSPACE-complete. If regular expressions are extended to allow also a squaring operator...

axiomatized by inference rules and can be decided by a PSPACE algorithm. The problem can be shown to be PSPACE-complete by reduction from the acceptance problem...

required, but runs for infinite time. The above proof holds for the case of PSPACE, but some changes need to be made for the case of NPSPACE. The crucial point...

With fellow graduate student David Lichtenstein, Sipser proved that Go is PSPACE hard. In quantum computation theory, he introduced the adiabatic algorithm...

C2P = PPPP C3P = PPPPPP ... The counting hierarchy is contained within PSPACE. By Toda's theorem, the polynomial hierarchy PH is entirely contained in...

a problem (the recognition of true quantified Boolean formulas) that is PSPACE-complete. Analogously, dependency quantified boolean formulas encode computation...

S2CID 206798056. 1988(over 740 citations) Regenar, James (April 1988). "A faster PSPACE algorithm for deciding the existential theory of the reals" (PDF). Technical...

later shown to be false, as the two acceptable complexity classes IP and PSPACE were shown to be equal despite IPA ⊊ PSPACEA for a random oracle A with...

the Turing machine. Some important corollaries of the theorem include: PSPACE = NPSPACE That is, the languages that can be recognized by deterministic...

the outcome in Snort is PSPACE-complete on general graphs. This is proven by reducing partizan node Kayles, which is PSPACE-complete, to a game of Snort...

follows because the game is P-complete by the circuit value problem and PSPACE-complete if an exponential number of marbles is allowed. The device has...

{\displaystyle \mu (\varphi )=0} . Moreover this problem has been shown to be PSPACE-complete. The following logics have the zero-one law: First-order logic...

otherwise, Cut can win. Unlike some other connection games, which can be PSPACE hard, optimal moves for the undirected switching game can be found in polynomial...

center, determining whether the current player has a winning strategy is PSPACE-hard. Schmittberger, R. Wayne (1992). New Rules for Classic Games. John...

Deciding the winner of an arbitrary finite poset game is PSPACE-complete. This means that unless P=PSPACE, computing the Grundy value of an arbitrary poset game...

interesting open problem". Only in 2020 it was proved that the game is PSPACE-Complete. Acyclic coloring. Every graph G {\displaystyle G} with acyclic...

models with unlimited precision are unreasonably powerful (able to solve PSPACE-complete problems in polynomial time). The transdichotomous model makes...

inside the black hole. Access to a CTC may allow the rapid solution to PSPACE-complete problems, a complexity class which, while Turing-decidable, is...

poly(n) is in PSPACE. On the other hand, if the question is whether the body eventually reaches the destination ball, the problem is PSPACE-hard. These...

collapses to SP 2 complexity class. There are stronger conclusions possible if PSPACE, or some other complexity classes are assumed to have polynomial-sized circuits;...

under some type of many-one reducibility, including P, NP, L, NL, co-NP, PSPACE, EXP, and many others. It is known for example that the first four listed...

Maker-Breaker game called an Avoider-Enforcer game. Maker-Breaker game is PSPACE-complete even if the size of each set is restricted to 5. The first result...

multiplicatives and additives (i.e., exponential-free). MALL entailment is PSPACE-complete. Multiplicative-exponential linear logic (MELL): only multiplicatives...

to the class of all GLP-spaces. The problem of being a theorem of GLP is PSPACE-complete. So is the same problem restricted to only variable-free formulas...

any given Sokoban puzzle is solvable is a problem known to be NP-hard and PSPACE-complete. In artificial intelligence research, Sokoban serves as an experimental...

sentence has probability tending to zero or to one is high: the problem is PSPACE-complete. If a first-order graph property has probability tending to one...

reflective objects represented by a system of rational linear inequalities is PSPACE-hard. For any dimension equal to or greater than 2, ray tracing with a finite...

between the online and offline algorithms' performance. This problem is PSPACE-complete. There are many formal problems that offer more than one online...

reasonable geometric (not algebraic) computation problems are solvable in PSPACE. Later, he extended these complexity results to polynomial input systems...

implies also equivalence of quantum and classical computation (both in PSPACE). If Lloyd's prescription holds, quantum computations would be PP-complete...

original paper analysed the complexity of the problem and reported it to be PSPACE-complete. It was also shown that finding an optimal path in the case where...

link]". Logic Journal of the IGPL 22 (2014), pages 982-991. I. Shapirovsky, "PSPACE-decidability of Japaridze's polymodal logic". Advances in Modal Logic 7...

solved efficiently also for NFAs. The non-universality problem for NFAs is PSPACE complete since there are small NFAs with shortest rejecting word in exponential...

Valiant, and strengthening the case in the negative for the question if PSPACE=P. Ryan Williams is married to Virginia Vassilevska Williams, also a theoretical...

pure strategies in the game. Subsequently, it has been shown that it is PSPACE-complete to find any of the solutions that can be obtained with the Lemke–Howson...

classes P, NP and PSPACE are closed under (many-one, "Karp") polynomial-time reductions. The complexity classes L, NL, P, NP and PSPACE are closed under...

all-powerful prover and a verifier that implements a BPP algorithm. IP = PSPACE. However, if it is required that the verifier be deterministic, then IP...

grammar, or by an arbitrary deterministic context-sensitive grammar, is a PSPACE-complete problem. List of parser generators for context-sensitive languages...

question, such as the emptiness problem for non-erasing stack automata, are PSPACE-complete. The emptiness problem in machine learning and formal languages...

) {\displaystyle {\rm {{Sat}([\exists ^{n}\forall \exists ]_{=})}}} are PSPACE-complete (Section 5.4.3). Börger et al. (2001) describes the level of computational...

Lemmings is NP-hard. Later, Giovanni Viglietta showed that the task is PSPACE-complete, even for levels where there is only one lemming to save. In 2010...

solving Hex on an N×N board is unlikely as the problem has been shown to be PSPACE-complete.[citation needed] If Hex is played on an N×(N + 1) board then the...

closed timelike curves, a computational complexity class equal in power to PSPACE Pure Car and Truck Carrier, a type of roll-on/roll-off cargo ship designed...

Wolfe in their book Mathematical Go. Go endgames have been proven to be PSPACE-hard if the absolute best move must be calculated on an arbitrary mostly...

Ofer Grossman proved that the problem of finding a winning strategy is PSPACE-hard in two kinds of games in which strategy-stealing arguments were used:...

Miltersen prove that SRS lies in the counting hierarchy (which is contained in PSPACE). Specifically, they show that SRS lies in PPPPPPP, in the fourth level...

wins), Schaefer proved in 1978 that deciding the outcome of these games is PSPACE-complete (the same holds for the partisan versions, in which, for every...

building up arithmetic functions. PSPACE Solvable with polynomial space. PSPACE-complete The hardest problems in PSPACE. PTAS Polynomial-time approximation...

Euclidean TSP is known to be in the Counting Hierarchy, a subclass of PSPACE. With arbitrary real coordinates, Euclidean TSP cannot be in such classes...

many other areas of computational complexity, such as the proof that IP=PSPACE. In addition, PIT has applications to Tutte matrices and also to primality...

class AM[poly(n)] is equal to the class, IP, which is known to be equal to PSPACE and is widely believed to be stronger than the class AM[2]. MA is contained...

strategy in the game represented by Φ {\displaystyle \Phi } . FORMULA-GAME is PSPACE-complete because it is exactly the same decision problem as True quantified...

and strengthening the case in the negative for the question of whether PSPACE=P. A related phenomenon to catalytic computing occurs in the study of space-efficient...

tricked by the all-powerful prover machine. For example, the class IP equals PSPACE, but if randomness is removed from the verifier, we are left with only NP...

decidable in exponential time These are similar to the definitions of P, PSPACE, and EXPTIME, considering the resources used by an ATM rather than a deterministic...

deterministic methods. However, all motion planning methods are subject to the PSPACE-hardnesss of classical motion planning even without dynamics, which means...

AG(EF(p)). Model checking and satisfiability against an LTL formula are PSPACE-complete problems. LTL synthesis and the problem of verification of games...

semantics. We label states. QCTL* = QCTL = MSO over graphs. Model checking is PSPACE-complete but satisfiability is undecidable. A reduction from the model-checking...

that for simply typed lambda calculus the type inhabitation problem is PSPACE-complete. For other calculi, like System F, the problem is even undecidable...

consider that when only one prover is present, we can only recognize all of PSPACE; the verifier's ability to "cross-examine" the two provers gives it great...

computationally difficult: sudoku is NP-complete, Rush Hour and reversi are PSPACE-complete, and chess is EXPTIME-complete. Beyond proving new results along...

over a signal is EXPSPACE-complete, while satisfiability for MITL0,∞ is PSPACE-complete. R. Alur, T. Feder, and T.A. Henzinger. The Benefits of Relaxing...

= NSPACE(O(n)), where CSL is the class of context-sensitive languages. PSPACE = NPSPACE = ⋃ k ∈ N N S P A C E ( n k ) {\displaystyle \bigcup _{k\in \mathbb...

32nd AMC Symposium on Theory of Computing: 608–617. Watrous, J (2003). "PSPACE has constant-round quantum interactive proof systems". Theoretical Computer...

proof that the type inhabitation problem in simply typed lambda calculus is PSPACE-complete, lower bounds on simply typed lambda calculus, logical relations...

function assumption in the space hierarchy theorem. L = DSPACE(O(log n)) PSPACE = ⋃ k ∈ N D S P A C E ( n k ) {\displaystyle \bigcup _{k\in \mathbb {N}...

of the reals § Complete problems Karp's 21 NP-complete problems List of PSPACE-complete problems Reduction (complexity) Grigoriev & Bodlaender (2007)....

of finite-state automata, equivalence is decidable, and the problem is PSPACE-complete. Further, in the case of deterministic pushdown automata, equivalence...

there is no polynomial-time algorithm to minimize general NFAs unless P = PSPACE, an unsolved conjecture in computational complexity theory that is widely...

deterministic classes are known to be equal, so that for example we have PSPACE = NPSPACE. Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern...

polynomial number of processors are required for some PSPACE-complete problem, then it would show that PSPACE = P, a major unresolved hypothesis that is expected...

complexity theory, a problem is assigned to a complexity class — such as P or PSPACE — by analysing the resource consumption (time, space) of a Turing machine...

derivability problem (for rules or formulas) in these logics, which is PSPACE-complete. Admissibility in propositional logics is closely related to unification...

results in complexity theory, including the time hierarchy theorem, IP = PSPACE, derandomization, and the representation of ACC0 via SYM+ circuits. Murray...

model checking in CTL* is not worse than that of LTL: they both lie in PSPACE. The language of well-formed CTL* formulae is generated by the following...

real RAM unreasonable amounts of computational power, enabling it to solve PSPACE-complete problems in polynomial time. When analyzing algorithms for the...

questions of computational complexity theory: whether P and NP, NP and PSPACE, PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not. The gap of approximately...

Turing machines; for example, IPA≠PSPACEA for a random oracle A but IP = PSPACE. A machine with an oracle for the halting problem can determine whether...

Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello. A version...

logic parameterized over the sorts of locations and data can be shown to be PSPACE-complete. An algorithm for solving this fragment in DPLL(T)-based SMT solvers...

Deciding whether any plan exists for a propositional STRIPS instance is PSPACE-complete. Various restrictions can be enforced in order to decide if a plan...

\triangleright _{I}\neg \psi } . The satisfiability of ECL over signals is PSPACE-complete. A MTL-formula in positive normal form is defined almost as any...

the problem of determining whether an Atomix puzzle has a solution is PSPACE-complete. Some heuristic approaches have been considered. Several open source...

problem is solvable in polynomial time and its satisfiability problem is PSPACE-complete. Muddy children puzzle formalized with PAL: Here are some of the...

1991 Symposium on Theory of Computing) states that polynomial time equals PSPACE if and only if fixed-point logic equals partial fixed-point logic. At the...

but a negative answer means "don't know". The decision problem for SCT is PSPACE-complete; however, there exists an algorithm that computes an approximation...

extended this result to show that the model could also be used to solve PSPACE problems in polynomial time. Deutsch shows that quantum computation with...

from the initial state and check if some final state can be reached. It is PSPACE-complete to test, given an NFA, whether it is universal, i.e., if there...

\mathbb {N} }{\mathsf {DTIME}}\left(2^{2^{n^{k}}}\right).} We know P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ELEMENTARY. 2-EXPTIME can...

entry point to the program, is reproduced here: GLOBAL STATIC (<STATUS 5;PSPACE 10001; TEMPLATE>) PROC KERMIT_THE_FROG IS ((<LIT "COMMAND">) REF()BYTE OPTION...

When transitive closure is added to second-order logic instead, we obtain PSPACE. Since the 1980s Oracle Database has implemented a proprietary SQL extension...

the case for showing that the true quantified Boolean formula problem is PSPACE-complete. This is because the need for memory in such reduction constructions...

automaton and checking whether it accepts the empty language. This problem is PSPACE-complete. The universality problem of non-deterministic timed automaton...

{\mathsf {P}}^{\#{\mathsf {P}}}={\mathsf {P}}^{\mathsf {PP}}\subset {\mathsf {PSPACE}}} Also, P H ⊂ P # P [ 1 ] {\displaystyle {\mathsf {PH}}\subset {\mathsf...

between the online and offline algorithms' performance. This problem is PSPACE-complete. Many formal problems offer more than one online algorithm as a...

conjunctive queries and are thus at least as hard (in fact, relational algebra is PSPACE-complete with respect to combined complexity and is therefore even harder...

complexity class C {\displaystyle C} , in particular NP-hard (but often also PSPACE-hard, PPAD-hard, etc.). This means that they are at least as hard as any...

method P (complexity) NP (complexity) NP-completeness NP-hardness EXPTIME PSPACE BPP (complexity) BQP Undecidable problem Halting problem Rice's theorem...

interactive proof systems Karloff-Nisan and Shamir, including the result IP = PSPACE. In the area of game theory, more specifically of non-cooperative games...

whereas FIXP is conjectured to be much harder, and lie in the "harder" end of PSPACE. Computing an approximate Nash equilibrium to any factor smaller than 1/2...

sentence can be done more quickly than exponential time, as the problem is PSPACE-complete. The Rado graph is ultrahomogeneous, and thus is the Fraïssé limit...

and thus ADL is strictly more brief than STRIPS. ADL planning is still a PSPACE-complete problem. Most of the algorithms polynomial space even if the preconditions...

algorithm, showing that the solubility problem for word equations is in PSPACE. In 2006, Plandowski and Wojciech Rytter showed that minimal solutions of...

determining whether a given sentence has probability tending to zero or to one is PSPACE-complete. A similar analysis has been performed for more expressive logics...

checking, satisfiability and validity problems of linear modal μ-calculus are PSPACE-complete. Actually, the complexity of the satisfiability problem of graded...

"Fixed-parameter tractability and completeness. IV. On completeness for W[P] and PSPACE analogues", Annals of Pure and Applied Logic, 73 (3): 235–276, doi:10...

It is indeed unambiguous as there exists only one nth last letter. Three PSPACE-hard problems for general NFA belong to PTIME for DFA and are now considered...

theory, the Abiteboul–Vianu Theorem states that polynomial time is equal to PSPACE if and only if fixed point logic is the same as partial fixed point logic...

poly-logarithmic runtime in κ {\displaystyle \kappa } would imply that BQP is equal to PSPACE, which is believed to be false. The dominant source of error is the application...

the value of such a game up to a multiplicative factor is known to be in PSPACE. Determining whether a pure Nash equilibrium exists is a Σ 2 P {\displaystyle...

the problem was established by Richard Statman in 1979, who showed it was PSPACE-complete and hence at least as hard as deciding equations of Boolean algebra...

Preprocessor – Primitive recursive function – Programming language – Prolog – PSPACE-complete – Pulse-code modulation (PCM) – Pushdown automaton – Python QuarkXPress...

smallest examples.[H88] A simpler method, showing also that the problem is PSPACE-complete, was provided in 2005 by Kirsten. Earlier, in 1979, Hashiguchi...

polynomial-time algorithms, while retaining a polynomial overall running time. PSPACE (with restricted oracle access mechanism) is also self-low, and this can...

of certain elements in this group. This is supposed to be hard, at least PSPACE-complete.[dubious – discuss] For this hash, an attack was eventually discovered...

Retrieved 1 August 2016. Holpuch, Jan. "EU.ODS.cz / ODS a volby do EP". euods.pspace.cz. Archived from the original on 10 October 2007. Retrieved 15 March 2017...

n)-bit bitstrings), SL (the analogous class for undirected graphs), and PSPACE (the class of problems that may be characterized by reachability in implicit...

implies that finding a Nash equilibrium reachable from a specified state is PSPACE-complete. For every problem in the complexity class PLS (essentially, every...