1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ This just equals PSPACE itself. $\endgroup$
    – Emil Jeřábek
    Sep 21 at 10:40
  • $\begingroup$ Savitch's theorem $\endgroup$
    – Peter Shor
    Sep 21 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
    Sep 21 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$
    – Emil Jeřábek
    Sep 21 at 12:01

0

Reset to default

Your Answer

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