<p>Let $\mathsf{coIP}$ denote the problem of returning the negation of the inner product. It has roughly the same complexity as $\mathsf{IP}$ since we can add to both players an extra $1$ bit. It is known that the deterministic communication complexity of a decision problem is upper bounded by the product of the non-deterministic complexities of the problem and its complement. Since $\mathsf{IP}$ has deterministic complexity $\Omega(n)$, it follows that the non-deterministic complexity of $\mathsf{IP}$ and $\mathsf{coIP}$ is $\Omega(\sqrt{n})$, and in particular $\mathsf{IP} \notin \mathsf{NP}^{cc} \cup \mathsf{coNP}^{cc}$.</p>

<p><a href="http://iiis.tsinghua.edu.cn/uploadfile/2012/0223/20120223094853773.pdf" rel="nofollow">Sun, Wang and Yu</a> showed that the non-deterministic communication complexity of $\mathsf{IP}$ is in fact $\Omega(n)$, even under the promise that the answer is either $0$ or $1$ (as an integer value).</p>

<p>In the related $\mathsf{MA}$ model, in which we demand perfect completeness but only constant soundness, there is an $O(\sqrt{n}\log n)$ protocol due to Aaronson and Wigderson almost matching Klauck's $\Omega(\sqrt{n})$ lower bound; see for example <a href="http://www.cs.toronto.edu/~toni/Courses/PvsNP/Lectures/lecture11.pdf" rel="nofollow">Pitassi's lecture notes</a>.</p>

CC BY-SA 3.0
2014-12-20T21:14:48.873Z
No,  of both since it's almost the same.
Yuval Filmus
CC BY-SA 3.0
2014-12-20T21:53:58.737Z
I mean complexity of disj and set intersection are very separate in non-det setting. I am just asking if there is an easy way to see complexity of ip and coip are similar.
Turbo
CC BY-SA 3.0
2014-12-20T22:37:12.940Z
@Turbo If you add to both inputs an extra bit which is fixed at 1 then you invert the result.
Yuval Filmus
CC BY-SA 3.0
2015-01-27T12:06:42.237Z
Is $IP\notin \Pi_2^{cc}\cup\Sigma_2^{cc}$ known?
Turbo
CC BY-SA 3.0
2014-12-20T20:11:52.277Z
2014-12-20T20:11:52.277Z
Yuval Filmus
<p>Is it known that $\mathsf{IP}\notin\mathsf{NP}^{cc}\cup\mathsf{coNP}^{cc}$ where $\mathsf{IP}$ is inner product communication complexity problem? Where is the classification of $\mathsf{IP}$ currently in?</p>

<communication-complexity>
Classification of a specific problem
Turbo
# Classification of a specific problem

(Asked by: username_0 on 2014-12-20)

Is it known that $\mathsf{IP}\notin\mathsf{NP}^{cc}\cup\mathsf{coNP}^{cc}$ where $\mathsf{IP}$ is inner product communication complexity problem? Where is the classification of $\mathsf{IP}$ currently in?

**Tags:** communication-complexity

---

## 1 answers

### Answer by username_1 on 2014-12-20. Score: 4 | Accepted answer

Let $\mathsf{coIP}$ denote the problem of returning the negation of the inner product. It has roughly the same complexity as $\mathsf{IP}$ since we can add to both players an extra $1$ bit. It is known that the deterministic communication complexity of a decision problem is upper bounded by the product of the non-deterministic complexities of the problem and its complement. Since $\mathsf{IP}$ has deterministic complexity $\Omega(n)$, it follows that the non-deterministic complexity of $\mathsf{IP}$ and $\mathsf{coIP}$ is $\Omega(\sqrt{n})$, and in particular $\mathsf{IP} \notin \mathsf{NP}^{cc} \cup \mathsf{coNP}^{cc}$.

[Sun, Wang and Yu](http://iiis.tsinghua.edu.cn/uploadfile/2012/0223/20120223094853773.pdf) showed that the non-deterministic communication complexity of $\mathsf{IP}$ is in fact $\Omega(n)$, even under the promise that the answer is either $0$ or $1$ (as an integer value).

In the related $\mathsf{MA}$ model, in which we demand perfect completeness but only constant soundness, there is an $O(\sqrt{n}\log n)$ protocol due to Aaronson and Wigderson almost matching Klauck's $\Omega(\sqrt{n})$ lower bound; see for example [Pitassi's lecture notes](http://www.cs.toronto.edu/~toni/Courses/PvsNP/Lectures/lecture11.pdf).

> **Comments:**
> **username_1**: No,  of both since it's almost the same.  
> **username_0**: I mean complexity of disj and set intersection are very separate in non-det setting. I am just asking if there is an easy way to see complexity of ip and coip are similar.  
> **username_1**: @Turbo If you add to both inputs an extra bit which is fixed at 1 then you invert the result.  
> **username_0**: Is $IP\notin \Pi_2^{cc}\cup\Sigma_2^{cc}$ known?  

---

