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

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. 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 NC. The first known NP-complete problem was the Boolean satisfiability problem (SAT). This is the problem of whether there are assignments of truth values to variables that make a boolean expression true. For example, one instance of SAT would be the question of whether the following is true: The SAT problem can be generalized to the quantified Boolean formula problem (QBF), an important PSPACE-complete problem that allows both universal and existential quantification over the values of the variables: The proof of that QBF is a PSPACE-complete... less