5
$\begingroup$

The celebrated proof that IP = PSPACE relies on an interactive proof for the QBF problem.

Is there any other "natural" interactive proof for a PSPACE-hard problem other than QBF?

(of course, since QBF is PSPACE-complete, such a proof exists via a reduction to QBF; I ask for a direct interactive proof that does not go through the reduction).

$\endgroup$

0

Your Answer

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