1
$\begingroup$

What are some examples problems with a direct proof that they are in $\mathsf{IP}$, other than Graph Non-Isomphism?

I have been looking for a while, but no luck so far.

$\endgroup$
  • 3
    $\begingroup$ Well, IP=PSPACE, so you might consider some PSPACE-complete problems, such as TQBF, en.wikipedia.org/wiki/True_quantified_Boolean_formula $\endgroup$ – Aryeh Jan 31 '17 at 17:48
  • $\begingroup$ I'm looking for a direct proof, @Aryeh but thank you. $\endgroup$ – Sefi Erlich Jan 31 '17 at 17:51
  • 9
    $\begingroup$ The proof of IP = PSPACE is a direct construction of an interactive protocol for TQBF. Chapter 8 of Arora - Barak has protocols for GNI, quadratic nonresiduosity, #SAT, TQBF, and the permanent. $\endgroup$ – Sasho Nikolov Jan 31 '17 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.