Inspired by the 2 definitions (theorems) I am aware of, that are as follows.

  1. A language L belongs to QMA if there exists a BQP verifier V.
  2. A language L belongs to NP if there exists a P verifier V.

Now I am curious about what's the complexity class A, such that the following statement holds. A language L belong to A if there exists a PSPACE verifier V. Is there an alternate characterization of A? Is there a good name for such a class a A for an arbitrary class X?

  • $\begingroup$ This just equals PSPACE itself. $\endgroup$ Commented Sep 21, 2023 at 10:40
  • $\begingroup$ Savitch's theorem $\endgroup$ Commented Sep 21, 2023 at 10:41
  • $\begingroup$ @PeterShor Is there a name for a general version of the theorem that connect NTIME(f(n))-DTIME(f(n)), NSPACE(f(n))-DSPACE(f(n)) this way, which would yield this result when combined with Savitch's theorem? I am only familiar with the concrete proof for NP-P. $\endgroup$
    – Ilk
    Commented Sep 21, 2023 at 10:51
  • 8
    $\begingroup$ You don’t need Savitch’s theorem. Just let the PSPACE machine try every possible witness in lexicographic order. (I’m assuming here that witnesses are required to have polynomial size. If you allow exponential-size witnesses for the verifier, then the class you get is NEXP rather than PSPACE.) $\endgroup$ Commented Sep 21, 2023 at 12:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.