What can be efficiently reduced to the Kolmogorov-random strings? (Q2576937)

Given a unary universal machine \(U\), one calls a string \(x\) incompressible or random iff \(U(p) \neq x\) for all binary inputs \(p\) shorter than \(x\). The authors study resource-bounded reductions to the co-r.e.\ set \(R\) of all incompressible strings and characterize complexity classes using this method. The following overview of the main results follows the numbering in the paper. Theorem 6. A set \(A\) is polynomial-time computable iff, for any universal machine \(U\), \(A\) is disjunctive polynomial-time truth-table reducible to the variant of \(R\) based on this \(U\). This result needs the quantification over all universal machines as the following result of the authors shows. Theorem 16. For every universal Turing machine \(U\) and every recursive function \(t\), there is a recursive set \(A\) which is disjunctive polynomial-time truth-table reducible to the variant of \(R\) based on \(U\), but which is not computable in deterministic space \(t(n)\). From now on, let \(R\) be based on one fixed universal machine. Theorem 8 is based on a conference version. Theorem 7. If a set \(A\) can be computed in nondeterministic exponential space, then it can be computed in nondeterministic polynomial time relative to \(R\). Theorem 8. If a recursive set \(A\) is polynomial-time bounded truth-table or conjunctive truth-table reducible to \(R\) then \(A\) is in P. The resource-bounded variant of linear truth-table reducibility [\textit{P. Odifreddi}, Classical recursion theory. Amsterdam etc.: North-Holland (1989; Zbl 0661.03029)] is called parity truth-table reducibility in this paper. For this reducibility, the authors show that for every recursively enumerable set \(A\) there is a universal machine \(U\) such that the padded version \(\{0^{2^x}: x \in A\}\) of \(A\) is parity truth-table reducible to \(R\) based on this machine \(U\). The same result holds also with disjunctive truth-table reducibility in place of parity truth-table reducibility. Note that the above results are for the plain version of Kolmogorov complexity, but the authors claim that Theorems 7 and 8 also work for prefix-free Kolmogorov complexity. Somehow, it is still an open problem whether Theorem 16 would also be true for prefix-free Kolmogorov complexity.