ECCC-Report TR10-060https://eccc.weizmann.ac.il/report/2010/060Comments and Revisions published for TR10-060en-usFri, 09 Apr 2010 13:46:50 +0300
Paper TR10-060
| A Separation of NP and coNP in Multiparty Communication Complexity |
Dmytro Gavinsky,
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2010/060We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to $k=(1-\epsilon)\log n$ players, where $\epsilon>0$ is any constant. Specifically, we construct a function $F:(\zoon)^k\to\zoo$ with co-nondeterministic
complexity $O(\log n)$ and Merlin-Arthur
complexity $n^{\Omega(1)}$.
The problem was open for $k\geq3$.Fri, 09 Apr 2010 13:46:50 +0300https://eccc.weizmann.ac.il/report/2010/060