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

<p>I have been looking for a while, but no luck so far. </p>

CC BY-SA 3.0
2017-01-31T17:48:27.323Z
Well, IP=PSPACE, so you might consider some PSPACE-complete problems, such as TQBF, https://en.wikipedia.org/wiki/True_quantified_Boolean_formula
Aryeh
CC BY-SA 3.0
2017-01-31T17:51:29.560Z
I'm looking for a direct proof,  @Aryeh but thank you.
Sefi Erlich
CC BY-SA 3.0
2017-01-31T18:32:27.497Z
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.
Sasho Nikolov
<cc.complexity-theory><interactive-proofs>
Examples of problems in $\mathsf{IP}$
Sefi Erlich
# Examples of problems in $\mathsf{IP}$

(Asked by: username_0 on 2017-01-31)

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.

**Tags:** cc.complexity-theory, interactive-proofs

> **Comments:**
> **username_1**: Well, IP=PSPACE, so you might consider some PSPACE-complete problems, such as TQBF, https://en.wikipedia.org/wiki/True_quantified_Boolean_formula  
> **username_0**: I'm looking for a direct proof,  @username_1 but thank you.  
> **username_2**: 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.  

---

## 0 answers

