Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR04-062 | 10th August 2004 00:00

On the P versus NP intersected with co-NP question in communication complexity


Revision #1
Authors: Stasys Jukna
Accepted on: 10th August 2004 00:00
Downloads: 2078


In this revised version one new result is added: we show that
NP is not a subset of BPP in the best-partition case. This
extends the same result of Rabin and Yao from the fixed-partition
case to the best-partition model.


TR04-062 | 28th July 2004 00:00

A note on the P versus NP intersected with co-NP question in communication complexity

Authors: Stasys Jukna
Publication: 28th July 2004 15:49
Downloads: 2834


We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and Yannakakis in 1983: here P=NP\cap coNP.
We show that in the best-partition case the situation is entirely different: here P is a proper subset of NP\cap coNP. This resolves an open question raised by Papadimitriou and Sipser in 1982. Actually, we prove even stronger separations in this case:
P is a proper subset of RP\cap coRP, and NP\cap coN is no longer a subset of BPP.


Comment #1 to TR04-062 | 13th August 2004 09:47

Comment #1
Authors: Stasys Jukna
Accepted on: 13th August 2004 09:47
Downloads: 2189


In the Revision 1 of ECCC Report Nr. 62 the following two changes should be
made (I am thankful to Hartmut Klauck for pointing to this):

1. In the last sentence of the abstract it should be "BPP is not a subset of NP".

2. In Theorem 2.1 and Lemma 3.1 replace "are constants" by "are O(\log n)".

ISSN 1433-8092 | Imprint