0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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}$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.