Question

Which of the following contains NP?

(a) PSPACE

(b) EXPSPACE

(c) Both (a) and (b)

(d) None of the mentioned

The question was posed to me in class test.

This intriguing question comes from Non Deterministic Polynomial Time in portion Intractable Problems of Automata Theory

Answer 1

Right option is (c) Both (a) and (b)

To elaborate: It is sufficient to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial time verifier. It is also contained in EXPTIME, since the same algorithm operates in exponential time.