202502151602

Tags : Complexity Theory

PSPACE

---

Definition

The collection of problems such that the amount of cells used in the work tape are bounded by some polynomial $p$ in terms of the size of the input are called $\text{P-SPACE}$

Some known problems in $\text{P-SPACE}$ are:

• Quantified Boolean Formulas
• Model Checking of FO
• Determining if a regular expression matches a string
• Type Inhabitation in P-SPACE

---

References

Complexity Classes