Failure of Symmetry of Information for Randomized Computations

Symmetry of Information (SoI) is a fundamental result in Kolmogorov complexity stating that for all n-bit strings x and y, K(x, y) = K(y) + K(x | y) up to an additive error of O(log n) [ZL70]. In contrast, understanding whether SoI holds for time-bounded Kolmogorov complexity measures is closely related to longstanding open problems in complexity theory and cryptography, such as the P versus NP question [LW95, Hir22] and the existence of one-way functions [HIL + 23, HLO24, HLN24].

In this paper, we prove that SoI fails for rKt complexity, the randomized analogue of Levin's Kt complexity [Lev84]. This is the first unconditional result of this type for a randomized notion of timebounded Kolmogorov complexity. More generally, we establish a close relationship between the validity of SoI for rKt and the existence of randomized algorithms approximating rKt(x). Motivated by applications in cryptography, we also establish the failure of SoI for a related notion called pKt complexity [HLO24], and provide an extension of the results to the average-case setting. Finally, we prove a near-optimal lower bound on the complexity of estimating conditional rKt, a result that might be of independent interest.

Our findings complement those of [Ron04], who demonstrated the failure of SoI for Kt complexity. In contrast, the randomized setting poses a significant challenge, which we overcome using insights from [KK25], structural results about rKt implied by SoI, and techniques from meta-complexity [Oli19] and the theory of computational pseudorandomness [TV07].