Question

Savitch theorem relates to which of the following:

(a) PSPACE=NPSPACE

(b) Alternating Turing Machine

(c) Time complexity

(d) None of the mentioned

I have been asked this question by my school principal while I was bunking the class.

I would like to ask this question from PSPACE topic in chapter Other Classes Of Problems of Automata Theory

Answer 1

Right choice is (a) PSPACE=NPSPACE

To explain: Some important conclusions of Savitch theorem includes:

a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.

b) NL∈L2