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).



Your Answer

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