30 problems

Instance Complexity Conjecture. Every nonrecursive recursively enumerable set has hard instances.

Let $U$ be the reference monotone machine. The monotone complexity of a finite binary string $x$ is … Let ${\bf M}(x)$ denote the corresponding monotone a priori probability. Levin…

The paper considers several definitions of the complexity $K_*(y\mid x*)$, including definitions based on minimal prediction error and an encoding-free characterization by non-nega…

Fix a base theory $\mathcal S$ and let $R$ be the set of Kolmogorov-random strings defined using the fixed universal machine and additive constant. Let $N_R^{\mathcal S}$ be the ma…

Fix a universal Turing machine $U$, a constant $c_U$, and let $R$ be the set of strings $x$ satisfying $K_U(x)\geq |x|-c_U$, where $K_U(x)$ is the plain Kolmogorov complexity of…

Simplicity–convergence conjecture. Simpler models converge faster than more complex or artificial ones.

Remaining-pairs conjecture. For every remaining pair of objects $X,Y$, the answer to the second question is negative.

Small-object conjecture. For every small object $X$, the answer to the first question is negative: there do not exist constants $c,d$ such that

Noncompression subset conjecture. For any set $X$ and any set $A\subseteq\mathbb{N}$ of lower density $\delta$, there is an infinite subset $B\subseteq A$ such that for infinitely…

Density-sensitive uniform-threshold conjecture. For any set $A\subseteq\mathbb{N}$ of lower density $\delta$, there is a number $N$ and a string $\tau$ of length at most…

Uniform finite-threshold conjecture. For any set $A\subseteq\mathbb{N}$, there is a number $N$ such that for any string $\sigma$,

Let $R$ be the set of Kolmogorov-random strings, and let $t$ be a proof-length bound for statements asserting that no proof of $x\in R$ has length at most $t$. Exhaustive-search co…

Let $R^*$ be the class of strings defined using an oracle $O$ for the program $p$ and a compression threshold $|p|\leq f(|x|)$, for any decreasing function $f$. Let $\mathcal{S}$ a…

Let $R$ be the set of Kolmogorov-random binary strings, where $x\in R$ means that no program of length at most $|x|/2$ outputs $x$. Let $\mathcal{S}$ and $\mathcal{T}$ be consisten…

Let $\mathcal{T}$ be a finitely axiomatized theory. Consider $\textbf{P}$-uniform families of propositional tautologies encoding statements of the form “there is no $\mathcal{T}$ p…

Shift-invariant randomness question. What properties of a finite sequence of heads and tails make us reject the conjecture that it was generated by some shift-invariant random proc…

Search-to-profile reduction. Given this information, one can find, via a polynomial probabilistic algorithm, strings $y_1',\ldots,y_m'$ such that the tuple…

Consider the algebra of invariant properties obtained by identifying invariant sets whose symmetric difference is negligible. Let $\mathbf{c}$ be the class generated by computable…

Let $X$ and $Y$ be infinite binary sequences, and let an oracle computation of $X$ by $Y$ have an oracle-use function measuring how many bits of $Y$ are queried to compute the firs…

Let $L_3$ be the language of maximally complex words for nondeterministic automatic complexity over the alphabet ${0,1,2}$, and let $\operatorname{coCFL}$ denote the complements of…

Conjecture. The same result holds for every 2-random sequence $\omega$.

Disjunctive Kolmogorov-complexity axioms conjecture. These axioms should suffice to prove every true statement of the form

Let $y$ be a binary sequence, and let $K(y_1^n)$ denote the prefix-free Kolmogorov complexity of its first $n$ bits. Write ${\cal R}$ for the class of Martin-Löf random binary sequ…

Equivalence conjecture. The definition of K-triviality due to Melnikov and Nies for computable Polish spaces is equivalent to being low for $(\mathcal{X},\mu)$-randomness on every…

Kolmogorov-complexity analogue conjecture. There exist functions $f(n)$ and $g(n)$ such that $f(n)=o(n)$ and $g(n)=o(n)$, and for all strings $A,B,C,D$ satisfying