PSPACE

In complexity theory, PSPACE denotes the class of decision problems that can be decided by deterministic Turing machines with polynomiellem place.

Alternative characterizations

By the Theorem of Savitch PSPACE is equal to the class NPSPACE, the class of space on polynomiellem decidable by a nondeterministic Turing machine problems.

For the complexity class IP that contains all decision problems that have an interactive proof system, then: IP = PSPACE.

Even for the class of AP recognized by alternating Turing machines in polynomial time languages ​​applies AP = PSPACE.

If one-way functions exist, CZK CZK applies to the class of languages ​​that exist knowledge proofs for the (computational ) zero, also = IP = PSPACE.

Problems in PSPACE

There are many problems in PSPACE, leave to which reduce all other PSPACE problems in polynomial time. Of these so-called PSPACE - complete problems, it is assumed that they are not in NP.

The canonical PSPACE - complete problem is the satisfiability problem for quantified boolean formulas.

Another PSPACE -complete problem is to decide whether a given word from a given context-sensitive grammar can be generated.

Relation to other complexity classes

The relationship to other known complexity classes is as follows:

It is believed that all of the above inclusions are genuine:

The inclusion NP PSPACE follows from the fact that only needs to be shown for any NP-hard problem that it is in PSPACE. This is for example the case for SAT: although there are an exponential number of assignments for the variables, but each of these assignments can be saved in polynomiellem place. Thus, all assignments can be sequentially enumerated and tested, making SAT can be answered, and thus all other problems in NP.