
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 coNP⊈MA in the number-on-forehead model of multiparty communication complexity for up to k=(1−ϵ)logn players, where ϵ>0 is any constant. Specifically, we construct an explicit function F:({0,1}n)k→{0,1} with co-nondeterministic complexity O(logn) and Merlin-Arthur complexity nΩ(1). The problem was open for k≥3. As a corollary, we obtain an explicit separation of NP and coNP for up to k=(1−ϵ)logn players, complementing an independent result by Beame et al. (2010) who separate these classes nonconstructively for up to k=2(1−ϵ)n players.