Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with best-partition protocols:
TR04-062 | 28th July 2004
Stasys Jukna

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

Revisions: 1 , Comments: 1

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 ... more >>>

ISSN 1433-8092 | Imprint