Volume 6 (2010)
Article 10 pp. 227-245

A Separation of NP and coNP in Multiparty Communication Complexity

Received: January 4, 2010

Published: November 16, 2010

Published: November 16, 2010

**Keywords:**multiparty communication complexity, nondeterminism, Merlin-Arthur computations, separations and lower bounds

**Categories:**complexity theory, communication complexity, multiparty communication complexity, lower bounds, separation of complexity classes, nondeterministic, Merlin, Arthur

**ACM Classification:**F.1.3, F.2.3

**AMS Classification:**68Q17, 68Q15

**Abstract:**
[Plain Text Version]

We prove that $ \mathsf{coNP} \not\subseteq \mathsf{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 an explicit function $F:\left(\{0,1\}^n\right)^k\to\{0,1\}$ with co-nondeterministic complexity $O(\log n)$ and Merlin-Arthur complexity $n^{\Omega(1)}.$ The problem was open for $k\geq3.$ As a corollary, we obtain an explicit separation of $\mathsf{NP}$ and $\mathsf{coNP}$ for up to $k=(1-\epsilon)\log n$ players, complementing an independent result by Beame et al. (2010) who separate these classes nonconstructively for up to $k = 2^{(1-\epsilon)n}$ players.