7 problems

Let $K$ be a fixed prefix-free Kolmogorov complexity and define, for reals $x,y\in\mathbb{R}$, $x\leq_K y$ if and only if there exists a constant $c\in\mathbb{N}$ such that for eve…

Conjecture: For every quantum polynomial-time sampler $S$ and every classical string $x$ that $S$ outputs with probability $\delta$, there is a quantum program for $x$ of length at…

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…

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 $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…