Goldberg, Halley ;
Kabanets, Valentine ;
Lu, Zhenjian ;
Oliveira, Igor C.
Probabilistic Kolmogorov Complexity with Applications to AverageCase Complexity
Abstract
Understanding the relationship between the worstcase and averagecase complexities of NP and of other subclasses of PH is a longstanding problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of metacomplexity: the complexity of problems that refer to the complexity of the input string x (e.g., given a string x, estimate its timebounded Kolmogorov complexity). In particular, [Shuichi Hirahara, 2021] employed techniques from metacomplexity to show that if DistNP ⊆ AvgP then UP ⊆ DTIME[2^{O(n/log n)}]. While this and related results [Shuichi Hirahara and Mikito Nanashima, 2021; Lijie Chen et al., 2022] offer exciting progress after a long gap, they do not survive in the setting of randomized computations: roughly speaking, "randomness" is the opposite of "structure", and upper bounding the amount of structure (timebounded Kolmogorov complexity) of different objects is crucial in recent applications of metacomplexity. This limitation is significant, since randomized computations are ubiquitous in algorithm design and give rise to a more robust theory of averagecase complexity [Russell Impagliazzo and Leonid A. Levin, 1990].
In this work, we develop a probabilistic theory of metacomplexity, by incorporating randomness into the notion of complexity of a string x. This is achieved through a new probabilistic variant of timebounded Kolmogorov complexity that we call pK^t complexity. Informally, pK^t(x) measures the complexity of x when shared randomness is available to all parties involved in a computation. By porting key results from metacomplexity to the probabilistic domain of pK^t complexity and its variants, we are able to establish new connections between worstcase and averagecase complexity in the important setting of probabilistic computations:
 If DistNP ⊆ AvgBPP, then UP ⊆ RTIME[2^O(n/log n)].
 If DistΣ^P_2 ⊆ AvgBPP, then AM ⊆ BPTIME[2^O(n/log n)].
 In the finegrained setting [Lijie Chen et al., 2022], we get UTIME[2^O(√{nlog n})] ⊆ RTIME[2^O(√{nlog n})] and AMTIME[2^O(√{nlog n})] ⊆ BPTIME[2^O(√{nlog n})] from stronger averagecase assumptions.
 If DistPH ⊆ AvgBPP, then PH ⊆ BPTIME[2^O(n/log n)]. Specifically, for any 𝓁 ≥ 0, if DistΣ_{𝓁+2}^P ⊆ AvgBPP then Σ_𝓁^{P} ⊆ BPTIME[2^O(n/log n)].
 Strengthening a result from [Shuichi Hirahara and Mikito Nanashima, 2021], we show that if DistNP ⊆ AvgBPP then polynomial size Boolean circuits can be agnostically PAC learned under any unknown 𝖯/polysamplable distribution in polynomial time. In some cases, our framework allows us to significantly simplify existing proofs, or to extend results to the more challenging probabilistic setting with little to no extra effort.
BibTeX  Entry
@InProceedings{goldberg_et_al:LIPIcs.CCC.2022.16,
author = {Goldberg, Halley and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.},
title = {{Probabilistic Kolmogorov Complexity with Applications to AverageCase Complexity}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {16:116:60},
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/16578},
URN = {urn:nbn:de:0030drops165785},
doi = {10.4230/LIPIcs.CCC.2022.16},
annote = {Keywords: averagecase complexity, Kolmogorov complexity, metacomplexity, worstcase to averagecase reductions, learning}
}
11.07.2022
Keywords: 

averagecase complexity, Kolmogorov complexity, metacomplexity, worstcase to averagecase reductions, learning 
Seminar: 

37th Computational Complexity Conference (CCC 2022)

Issue date: 

2022 
Date of publication: 

11.07.2022 