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...

complements of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE = PSPACE. The following relations are known between PSPACE and the complexity classes...

places it in the important complexity class PSPACE; with more work, it can be shown to be PSPACE-complete. Due to the large size of game complexities...

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....

\exists y\ \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...

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...

grid was unavailable. In 1981, the Stefan Reisch showed that Hex is PSPACE-complete. In 2002, the first explicit winning strategy (a reduction-type strategy)...

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

model Existential theory of the reals § Complete problems Karp's 21 NP-complete problems List of PSPACE-complete problems Reduction (complexity) Grigoriev...

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

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

puzzles was first shown to be NP-hard. Further work proved it is also PSPACE-complete. Solving non-trivial Sokoban puzzles is difficult for computers because...

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 first...

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

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 reduction...

undecidable problems Lists of unsolved problems List of NP-complete problems List of PSPACE-complete problems This article includes a list of lists....

Wiley & Sons, ISBN 0-471-90413-9. More precisely, this language is PSPACE-complete; see, for example, Wegener, Ingo (2005), Complexity Theory: Exploring...

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

List of hypothetical technologies List of NP-complete problems List of paradoxes List of PSPACE-complete problems List of undecidable problems List of...

often PSPACE-complete. The same is true of exponentially long games in which non-repetition is automatic. Another set of important EXPTIME-complete problems...

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

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....

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

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...

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, into...

is coNEXP-complete. This should be contrasted with the derivability problem (for rules or formulas) in these logics, which is PSPACE-complete. Admissibility...

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 and...

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. ∃...

Computer Othello refers to computer architecture encompassing computer hardware and computer software capable of playing the game of Othello. It was notably...

such as the emptiness problem for non-erasing stack automata, are PSPACE-complete. The emptiness problem is undecidable for context-sensitive grammars...