Editing PSPACE-complete (section)

==Theory==
A problem is defined to be PSPACE-complete if it can be solved using a polynomial amount of memory (it belongs to PSPACE) and every problem in PSPACE can be transformed in polynomial time into an equivalent instance of the given problem.{{r|garey-johnson}}

The PSPACE-complete problems are widely suspected to be outside the more famous complexity classes [[P (complexity)|P]] (polynomial time) and [[NP (complexity)|NP]] (non-deterministic polynomial time), but that is not known.{{r|arora-barak}} It is known that they lie outside of the class [[NC (complexity)|NC]], a class of problems with highly efficient [[parallel algorithm]]s, because problems in NC can be solved in an amount of space polynomial in the [[logarithm]] of the input size, and the class of problems solvable in such a small amount of space is strictly contained in PSPACE by the [[space hierarchy theorem]].

The transformations that are usually considered in defining PSPACE-completeness are polynomial-time [[many-one reduction]]s, transformations that take a single instance of a problem of one type into an equivalent single instance of a problem of a different type. However, it is also possible to define completeness using [[Turing reduction]]s, in which one problem can be solved in a polynomial number of calls to a subroutine for the other problem. It is not known whether these two types of reductions lead to different classes of PSPACE-complete problems.{{r|watanabe-tang}} Other types of reductions, such as many-one reductions that always increase the length of the transformed input, have also been considered.{{r|hitchcock-pavan}}

A version of the [[Berman–Hartmanis conjecture]] for PSPACE-complete sets states that all such sets look alike, in the sense that they can all be transformed into each other by polynomial-time [[bijection]]s.{{r|berman-hartmanis}}