Scholarlink

Denote by H the halting problem. Let \(R_U := \{ x |\textrm{C}_U(x) \ge |x| \}\) , where \(\textrm{C}_U(x)\) represents the plain Kolmogorov complexity of x under a universal decompressor U. We demonstrate the existence of a universal U such that H is solvable in polynomial time with access to the oracle \(R_U\) . This result resolves a problem posed by Eric Allender in [1] regarding the computational power of Kolmogorov complexity-based oracles.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the Computational Power of \(\textrm{C}\) -Random Strings

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Alexey Milovanov

摘要

Denote by H the halting problem. Let \(R_U := \{ x |\textrm{C}_U(x) \ge |x| \}\) , where \(\textrm{C}_U(x)\) represents the plain Kolmogorov complexity of x under a universal decompressor U. We demonstrate the existence of a universal U such that H is solvable in polynomial time with access to the oracle \(R_U\) . This result resolves a problem posed by Eric Allender in [1] regarding the computational power of Kolmogorov complexity-based oracles.