Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js
pdf icon
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
Download article from ToC site:
[PDF (276K)] [PS (1001K)] [Source ZIP]
Keywords: multiparty communication complexity, nondeterminism, Merlin-Arthur computations, separations and lower bounds
ACM Classification: F.1.3, F.2.3
AMS Classification: 68Q17, 68Q15

Abstract: [Plain Text Version]

We prove that coNP 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.