A Separation of NP and coNP in Multiparty Communication Complexity
We prove that NP differs from coNP and coNP is not a subset of MA in the number-on-forehead model of multiparty communication complexity for up to k = (1-ε)log(n) players, where ε>0 is any constant. Specifically, we construct a function F with co-nondeterministic complexity O(log(n)) and Merlin-Ar...
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Article |
| Publié: |
2010
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/1004.0817 http://arxiv.org/abs/1004.0817 |
| Tags: |
Pas de tags, Soyez le premier à ajouter un tag!
|