Abstract

We introduce a two-party communication complexity problem in which the probability of success by using a particular strategy allows the parties to detect with certainty whether or not some forbidden communication has taken place. We show that theprobability of success is bounded by nature; any conceivable method which gives a probability of success outside these bounds is impossible. Moreover, any conceivable method to solve the problem which gives a probability success within these bounds is possible in nature. This example suggests that a suitaby chosen set of communication complexity problems could be the basis of an information-theoretic axiomatization of quantum mechanics