论文标题
概率Kolmogorov复杂性的理论和应用
Theory and Applications of Probabilistic Kolmogorov Complexity
论文作者
论文摘要
近年来发现了Kolmogorov复杂性在学习[CIKK16]，电路复杂性[OPS19]，密码[LP20]，平均案例复杂性[HIR21]和证明搜索[KRA22]的各种应用[KRA22]。由于算法的运行时间是这些字段中的关键资源，因此在相应的参数中，考虑Kolmogorov复杂性的时变变种至关重要。尽管有一段时间以时期的Kolmogorov复杂性与理论计算机科学的不同领域之间的富有成果的相互作用已经闻名了一段时间（例如[[SIP83，KO91，ABK+06，AF09]，仅举几例），但上述结果已经引起了人们对这个话题的重新兴趣。 Kolmogorov复杂性的理论已被充分理解，但是众所周知，Kolmogorov复杂性的许多有用的结果和特性在时间结合的环境中持有。在应用时间结合的Kolmogorov复杂性中的方法和复杂性理论时，这会产生技术困难或导致有条件的结果。也许更重要的是，在许多情况下，有必要考虑随机算法。由于随机字符串具有很高的复杂性，因此在这种情况下，有时的Kolmogorov复杂性的经典理论可能是不合适的。 为了减轻这些问题并开发一种时间结合的Kolmogorov复杂性，在随机计算的设置中生存下来，最近的一些论文[OLI19，LO21，LOS21，GKLO22，LOZ22，LOZ22]探索了时间与kolmogorov的概率概念，例如，kolmogorov的复杂性，例如$ $ \ nathssf} $ \ rkt} $ \ mathsf {rk}^t $复杂性[LOS21]和$ \ Mathsf {pk}^t $ complextity [gklo22]。这些措施考虑了通过概率表示编码对象的不同方式。在这项调查中，我们提供了概率时间限制的Kolmogorov复杂性及其应用的介绍，突出了许多开放问题和研究方向。
Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have been discovered in recent years. Since the running time of algorithms is a key resource in these fields, it is crucial in the corresponding arguments to consider time-bounded variants of Kolmogorov complexity. While fruitful interactions between time-bounded Kolmogorov complexity and different areas of theoretical computer science have been known for quite a while (e.g., [Sip83, Ko91, ABK+06, AF09], to name a few), the aforementioned results have led to a renewed interest in this topic. The theory of Kolmogorov complexity is well understood, but many useful results and properties of Kolmogorov complexity are not known to hold in time-bounded settings. This creates technical difficulties or leads to conditional results when applying methods from time-bounded Kolmogorov complexity to algorithms and complexity theory. Perhaps even more importantly, in many cases it is necessary to consider randomised algorithms. Since random strings have high complexity, the classical theory of time-bounded Kolmogorov complexity might be inappropriate in such contexts. To mitigate these issues and develop a theory of time-bounded Kolmogorov complexity that survives in the setting of randomised computations, some recent papers [Oli19, LO21, LOS21, GKLO22, LOZ22] have explored probabilistic notions of time-bounded Kolmogorov complexity, such as $\mathsf{rKt}$ complexity [Oli19], $\mathsf{rK}^t$ complexity [LOS21], and $\mathsf{pK}^t$ complexity [GKLO22]. These measures consider different ways of encoding an object via a probabilistic representation. In this survey, we provide an introduction to probabilistic time-bounded Kolmogorov complexity and its applications, highlighting many open problems and research directions.
