Savitch's Theorem - Corollaries

Corollaries

Some important corollaries of the theorem include:

• PSPACE = NPSPACE
  • This follows directly from the fact that the square of a polynomial function is still a polynomial function. It is believed that a similar relationship does not exist between the polynomial time complexity classes, P and NP, although this is still an open question.
• NL ⊆ L2
  • A direct result of the construction of the proof.