Pspace-complete

PSPACE-complete

In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time (see complete (complexity)). The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, because a solution to any one such problem could easily be used to solve any other problem in PSPACE. These problems are widely suspected to be outside of the more famous complexity classes P and NP, but that is not known. It is known that they lie outside of the small class NC, since NC is contained in PolyL = DSPACE((log n)O(1))), which is strictly contained in PSPACE by the space hierarchy theorem.

Read more about Pspace-complete.