Symmetry of Information and One-Way Functions

Symmetry of information (in Kolmogorov complexity) is a concept that comes from formalizing the idea of how much information about a string y is contained in a string x. The situation is symmetric because it can be shown that the amount of information contained in the string y about the string x is almost exactly the same as that contained in x about y. In this paper we address symmetry of information in resource bounded environments. While we show that symmetry still holds in space bounded environments, it probably doesn't hold in time bounded environments. We show that if it holds for polynomial time bounds, then one-way functions cannot exist. 1 Introduction Keywords: computational complexity, Kolmogorov complexity, one-way functions. In probability theory, the phenomenon of dependence between random variables is well known. Cast in terms of classical Shannon entropy [Sha48, Sha49], the quantity of information in a random variable Y about another random variable X is I(X; Y ) =..