A Separation of NP and coNP in Multiparty Communication Complexity

Details A Separation of NP and coNP in Multiparty Communication Complexity A Separation of NP and coNP in Multiparty Communication Complexity

2010-04-06

arxiv.org/abs/1004.0817v1

Computer Science

Computational Complexity

Scientific paper

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-\epsilon)log(n) players, where \epsilon>0 is any constant. Specifically, we
construct a function F with co-nondeterministic complexity O(log(n)) and
Merlin-Arthur complexity n^{\Omega(1)}. The problem was open for k > 2.

Affiliated with

Also associated with

No associations

Rating

A Separation of NP and coNP in Multiparty Communication Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Separation of NP and coNP in Multiparty Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Separation of NP and coNP in Multiparty Communication Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-57152