Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-060 | 5th April 2010 23:54

#### A Separation of NP and coNP in Multiparty Communication Complexity

TR10-060
Authors: Dmytro Gavinsky, Alexander A. Sherstov
Publication: 9th April 2010 13:46
We 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$.