On the P versus NP intersected with co-NP question in communication complexity |
| |
Authors: | Stasys Jukna |
| |
Affiliation: | a Universität Frankfurt, Institut für Informatik, D-60054 Frankfurt, Germany b Institute of Mathematics and Informatics, LT-08663 Vilnius, Lithuania |
| |
Abstract: | We consider the analog of the P versus NP∩co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function f and its negation ¬f have small (poly-logarithmic in the number of variables) nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition model of communication this question was answered by Aho, Ullman and Yannakakis in 1983: here P=NP∩co-NP.We show that in the best partition model of communication the situation is entirely different: here P is a proper subset even of RP∩co-RP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982. |
| |
Keywords: | Computational complexity Communication complexity |
本文献已被 ScienceDirect 等数据库收录! |
|