5 problems

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…