<p>Inspired by the 2 definitions (theorems) I am aware of, that are as follows.</p>
<ol>
<li>A language L belongs to QMA if there exists
a BQP verifier V.</li>
<li>A language L belongs to NP if there exists a P verifier V.</li>
</ol>
<p>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?</p>

CC BY-SA 4.0
2023-09-21T10:40:58.383Z
This just equals PSPACE itself.
Emil Jeřábek
CC BY-SA 4.0
2023-09-21T10:41:31.223Z
[Savitch's theorem](https://en.wikipedia.org/wiki/Savitch%27s_theorem)
Peter Shor 
CC BY-SA 4.0
2023-09-21T10:51:48.727Z
@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.
Ilk
CC BY-SA 4.0
2023-09-21T12:01:39.983Z
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.)
Emil Jeřábek
<cc.complexity-theory><complexity-classes><pspace>
What complexity class is characterized by having PSPACE verifiers?
Ilk
# What complexity class is characterized by having PSPACE verifiers?

(Asked by: username_0 on 2023-09-21)

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?

**Tags:** cc.complexity-theory, complexity-classes, pspace
> **Comments:**
> **username_1**: This just equals PSPACE itself.  
> **username_2**: [Savitch's theorem](https://en.wikipedia.org/wiki/Savitch%27s_theorem)  
> **username_0**: @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.  
> **username_1**: 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.)  

---

## 0 answers

