Time-bounded Kolmogorov complexity

The $t$-time-bounded Kolmogorov complexity $K^t(x)$ of a string $x$ is the length of the shortest program that outputs $x$ within $t(|x|)$ steps. The assumption is that every efficient algorithm fails to compute $K^t(x)$ on at least an inverse-polynomial fraction of uniformly random $x$.

Assumption

Fix a universal Turing machine $U$. For a time bound $t:\mathbb{N}\to \mathbb{N}$ and $x\in \{0,1{\}}^{\ast }$,

$$K^t(x):=\min \left\{|\Pi |:U(\Pi ,1^{t(|x|)})=x\right\},$$

where $U(\Pi ,1^t)$ is the output of $U$ on the program $\Pi$ within $t$ steps — LP20.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{kt}}_{t,\calA}(\secpar)$}
\begin{algorithmic}
\State $x \getsr \bits^\secpar$
\State $k \gets \calA(1^\secpar, x)$
\Return $[k = K^t(x)]$
\end{algorithmic}
\end{algorithm}

For a polynomial $t(n)\ge (1+\epsilon )n$ with a constant $\epsilon >0$, $K^t$ is mildly hard on average if there is a polynomial $p$ such that for all efficient $\mathcal{A}$ and all sufficiently large $\lambda$,

$$\mathrm{Pr}\left[{\mathbf{G}}_{t,\mathcal{A}}^{\mathrm{kt}}(\lambda )=1\right]<1-\frac{1}{p(\lambda )}$$

— LP20.

Known Results

• Mild average-case hardness of Kᵗ ⇔ OWF: for every polynomial $t(n)\ge (1+\epsilon )n$, $K^t$ is mildly hard on average if and only if one-way functions exist — LP20.

Attacks

• Running every program of length at most $\ell$ on $U$ for $t(|x|)$ steps decides whether $K^t(x)\le \ell$ in time $2^{\ell +1}\cdot \mathrm{poly}(t(|x|))$ — standard.

Participates in

Builds on Time-bounded Kolmogorov complexity

• Mild average-case hardness of Kᵗ ⇔ OWF