ECCC-Report TR04-062https://eccc.weizmann.ac.il/report/2004/062Comments and Revisions published for TR04-062en-usFri, 13 Aug 2004 09:47:00 +0300
Comment 1
| |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2004/062#comment1In 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)".
Fri, 13 Aug 2004 09:47:00 +0300https://eccc.weizmann.ac.il/report/2004/062#comment1
Revision 1
| On the P versus NP intersected with co-NP question in communication complexity |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2004/062#revision1In 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.
Tue, 10 Aug 2004 00:00:00 +0300https://eccc.weizmann.ac.il/report/2004/062#revision1
Paper TR04-062
| A note on the P versus NP intersected with co-NP question in communication complexity |
Stasys Jukna
https://eccc.weizmann.ac.il/report/2004/062We 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.
<p>
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.
Wed, 28 Jul 2004 15:49:36 +0300https://eccc.weizmann.ac.il/report/2004/062