# A Separation of NP and coNP in Multiparty Communication Complexity - Computer Science > Computational Complexity

Abstract: We prove that NP differs from coNP and coNP is not a subset of MA in thenumber-on-forehead model of multiparty communication complexity for up to k =1-\epsilonlogn players, where \epsilon>0 is any constant. Specifically, weconstruct a function F with co-nondeterministic complexity Ologn andMerlin-Arthur complexity n^{\Omega1}. The problem was open for k > 2.

Author: Dmitry Gavinsky, Alexander A. Sherstov

Source: https://arxiv.org/