• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual Symposium on Theoretical Aspects of Computer Science(STACS 2004); 20040325-20040327; Montpellier; FR >What Can Be Efficiently Reduced to the K-Random Strings?
【24h】

What Can Be Efficiently Reduced to the K-Random Strings?

机译：可以有效地还原为K随机字符串吗？

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R_K. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the definition of Kolmogorov complexity. Among other results, we show that although for every universal machine U, there are very complex sets that are ≤ _(dtt)~p-reducible to R_K_U, it is nonetheless true that P = REG ∩ ∩_U{A:A ≤ _(dtt)~p R_K_U}. We also show for a broad class of reductions that the sets reducible to RK have small circuit complexity.
机译：我们研究一个问题，即是否可以通过对Kolmogorov随机字符串R_K的集合的有效归约性来表征复杂度类（例如PSPACE或NEXP）。我们表明，如果没有明确地解决在定义Kolmogorov复杂度时选择通用机器所引起的问题，就不可能提出这个问题。在其他结果中，我们表明，尽管对于每个通用机器U，都有非常复杂的集合，它们可≤R_K_U≤_（dtt）〜p-可归约，但P = REG∩_U{A：A≤_ （dtt）〜p R_K_U}。我们还针对大量的归约表明，可归结为RK的集合具有较小的电路复杂性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号