论文标题
最佳编码定理在时间遇到的Kolmogorov复杂性
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity
论文作者
论文摘要
Kolmogorov复杂性中的经典编码定理指出，如果算法通过具有前缀无域的算法对概率$δ$采样，则用k $（x）\ leq \ log log（1/δ） + O（1）$采样。 In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that if $x$ can be efficiently sampled with probability $δ$ then rKt$(x) = O(\log(1/δ)) + O(\log n)$, where rKt denotes the randomized analogue of Levin's Kt complexity.不幸的是，在将经典编码定理的应用传输到时键设置时，该结果通常不足，因为它实现了$ O（\ log（1/δ））$而不是信息理论的最佳$ \ log（1/δ）$。 我们显示了RKT的编码定理，$ 2 $。与以前的工作一样，我们的编码定理是有效的，从某种意义上说，它提供了一种多项式概率概率算法，当给定$ x $，采样器的代码和$δ$时，IT输出，概率$ \ ge ge 0.99 $，$ x $ $ x $的概率表示，证明了这种rkt的复杂性。 假设加密伪数生成器的安全性，我们表明没有有效的编码定理可以实现RKT $（x）\ leq（2 -o（1））\ cdot \ log \ log（1/δ） +$ $ poly $（\ log log n）$的界限。在较弱的假设下，我们在有效编码定理和具有接近最佳参数的存在定理之间表现出差距。 我们考虑pk $^t $复杂性[GKLO22]，这是RKT的一种变体，其中随机性是公开的，并且固定时间是固定的。我们观察到PK $^T $的最佳编码定理的存在，并采用此结果来建立Antunes and Fortnow定理的无条件版本[AF09]，该定理表征了所有p samplplable分布中平均多种态度的语言运行时间。
The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $δ$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/δ) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that if $x$ can be efficiently sampled with probability $δ$ then rKt$(x) = O(\log(1/δ)) + O(\log n)$, where rKt denotes the randomized analogue of Levin's Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a $O(\log(1/δ))$ bound instead of the information-theoretic optimal $\log(1/δ)$. We show a coding theorem for rKt with a factor of $2$. As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given $x$, the code of the sampler, and $δ$, it outputs, with probability $\ge 0.99$, a probabilistic representation of $x$ that certifies this rKt complexity bound. Assuming the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt$(x) \leq (2 - o(1)) \cdot \log(1/δ) +$ poly$(\log n)$. Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. We consider pK$^t$ complexity [GKLO22], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pK$^t$, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [AF09] which characterizes the worst-case running times of languages that are in average polynomial-time over all P-samplable distributions.
