Slide 1PSPACE definedGiorgi Japaridze Theory of ComputabilityThe Class PSPACEThe Class PSPACESection 8.2PSPACE defined 8.2.aGiorgi Japaridze Theory of ComputabilityDefinition 8.6 PSPACE is the class of languages that are decidable in polynomial space on a deterministic TM. In other words, PSPACE = SPACE(n) SPACE(n2) SPACE(n3) ... NPSPACE can be defined similarly. However, the latter is not a very interesting class because, as an immediate corollary of Savitch’s theorem, it coincides with PSPACE (squaring polynomial space again yields polynomial space). This is what we know (why?): P NP PSPACE=NPSPACE EXPTIME.We, however, do not know whether any of the three s can be replaced by =. Another set of huge open problems! It can be proven however that PEXPTIME. So, at least one of the three containments must be proper ( but not =), even though we do not know which
View Full Document
Unlocking...