Hirahara, Shuichi
Symmetry of Information from MetaComplexity
Abstract
Symmetry of information for timebounded Kolmogorov complexity is a hypothetical inequality that relates timebounded Kolmogorov complexity and its conditional analogue. In 1992, Longpré and Watanabe showed that symmetry of information holds if NP is easy in the worst case, which has been the state of the art over the last three decades. In this paper, we significantly improve this result by showing that symmetry of information holds under the weaker assumption that NP is easy on average. In fact, our proof techniques are applicable to any resourcebounded Kolmogorov complexity and enable proving symmetry of information from an efficient algorithm that computes resourcebounded Kolmogorov complexity.
We demonstrate the significance of our proof techniques by presenting two applications. First, using that symmetry of information does not hold for Levin’s Ktcomplexity, we prove that randomized Ktcomplexity cannot be computed in time 2^o(n) on inputs of length n, which improves the previous quasipolynomial lower bound of Oliveira (ICALP 2019). Our proof implements Kolmogorov’s insightful approach to the P versus NP problem in the case of randomized Ktcomplexity. Second, we consider the question of excluding Heuristica, i.e., a world in which NP is easy on average but NP ≠ P, from Impagliazzo’s five worlds: Using symmetry of information, we prove that Heuristica is excluded if the problem of approximating timebounded conditional Kolmogorov complexity K^t(x∣y) up to some additive error is NPhard for t ≫ y. We complement this result by proving NPhardness of approximating sublineartimebounded conditional Kolmogorov complexity up to a multiplicative factor of x^{1/(log log x)^O(1)} for t ≪ y. Our NPhardness proof presents a new connection between sublineartimebounded conditional Kolmogorov complexity and a secret sharing scheme.
BibTeX  Entry
@InProceedings{hirahara:LIPIcs.CCC.2022.26,
author = {Hirahara, Shuichi},
title = {{Symmetry of Information from MetaComplexity}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {26:126:41},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16588},
URN = {urn:nbn:de:0030drops165880},
doi = {10.4230/LIPIcs.CCC.2022.26},
annote = {Keywords: resourcebounded Kolmogorov complexity, averagecase complexity, pseudorandomness, hardness of approximation, unconditional lower bound}
}
11.07.2022
Keywords: 

resourcebounded Kolmogorov complexity, averagecase complexity, pseudorandomness, hardness of approximation, unconditional lower bound 
Seminar: 

37th Computational Complexity Conference (CCC 2022)

Issue date: 

2022 
Date of publication: 

11.07.2022 