Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with coNP:
TR10-060 | 5th April 2010
Dmitry Gavinsky, Alexander A. Sherstov

A Separation of NP and coNP in Multiparty Communication Complexity

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

more >>>

ISSN 1433-8092 | Imprint