Article ID Journal Published Year Pages File Type
10331307 Information Processing Letters 2005 5 Pages PDF
Abstract
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
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
On the P versus NP intersected with co-NP question in communication complexity
Authors
,