Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-060 | 5th April 2010 23:54

A Separation of NP and coNP in Multiparty Communication Complexity

RSS-Feed




TR10-060
Authors: Dmitry Gavinsky, Alexander A. Sherstov
Publication: 9th April 2010 13:46
Downloads: 1464
Keywords: 


Abstract:

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$.



ISSN 1433-8092 | Imprint