I want to prove that a problem is in NP. I have a witness (of polynomial size), and a verifier that runs in polynomial time. However, this verifier uses exponential space, becuase it has to generate strings of exponential size. Is this allowed?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If your verifier (a Turing machine) runs in polynomial time then it must also use polynomial space since you can write at most one tape cell (or a constant number of tape-cell in case of multi-tape machines) per time-step.
In other words $\mathsf{P} \subseteq \mathsf{PSPACE}$.
