| Pspace |
Articles about Pspace |
Information AboutPspace |
| CATEGORIES ABOUT PSPACE | |
| complexity classes | |
| closure operators | |
|
PSPACE is a strict superset of the set of Context-sensitive Languages . The following relationships are known between the classes ''' NL ''', ''' P ''', ''' NP ''', PSPACE, and ''' EXPSPACE ''': : : There are three symbols on the first line. It is known that at least one of them must be a , but it is not known which. It is widely suspected that all three are . A solution of the P Vs. NP question (whether the second is strict) is worth $1,000,000 . The hardest problems in PSPACE are the '''PSPACE-Complete''' problems. See ''' PSPACE-Complete ''' for examples of problems that are suspected to be in PSPACE but not in '''NP'''. OTHER CHARACTERIZATIONS An alternative characterization of PSPACE is the set of problems decidable by an Alternating Turing Machine in polynomial time, sometimes called '''APTIME''' or just '''AP'''. A logical characterization of PSPACE is that it is the set of problems expressible in Second Order Logic with the addition of a Transitive Closure operator. A full transitive closure is not needed; a commutative transitive closure and even weaker forms suffice. It is the addition of this operator that (possibly) distinguishes PSPACE from ''' PH '''. A major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular Interactive Proof System , the one defining the class ''' IP '''. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language. It should be able to convince the verifier with high probability if the string is in the language, but should not be able to convince it except with low probability if the string is not in the language. REFERENCES
|
|
|