• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Computing >KOLMOGOROV COMPLEXITY AND INSTANCE COMPLEXITY OF RECURSIVELY ENUMERABLE SETS
【24h】

KOLMOGOROV COMPLEXITY AND INSTANCE COMPLEXITY OF RECURSIVELY ENUMERABLE SETS

机译：递归可数集的Kolmogorov复杂性和实例复杂性

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

摘要

The way in which way Kolmogorov complexity and instance complexity affect properties of recursively enumerable (r.e.) sets is studied. The well-known 2 log n upper bound on the Kolmogorov complexity of initial segments of r.e. sets is shown to be optimal, and the Turing degrees of r.e. sets which attain this bound are characterized. The main part of the paper is concerned with instance complexity, introduced by Ko, Orponen, Schoning, and Watanabe in 1986, as a measure of the complexity of individual instances of a decision problem. They conjectured that for every r.e. nonrecursive set, the instance complexity is infinitely often at least as high as the Kolmogorov complexity. The conjecture is refuted by constructing an r.e. nonrecursive set with instance complexity logarithmic in the Kolmogorov complexity. This bound is optimal up to an additive constant. In the other extreme, the conjecture is established for many classes of complete sets, such as weak-truth-table-complete (wtt-complete) and Q-complete sets. However, there is a Turing-complete set for which it fails. [References: 16]
机译：研究了Kolmogorov复杂度和实例复杂度影响递归可枚举（r.e.）集的属性的方式。 r.e的初始段的Kolmogorov复杂度的众所周知的2 log n上限。集合被证明是最优的，图灵度为r.e.表征达到此界限的集合。本文的主要部分与实例复杂性有关，由Ko，Orponen，Schoning和Watanabe于1986年引入，以衡量决策问题单个实例的复杂性。他们猜想每一次在非递归集合中，实例复杂度通常至少与Kolmogorov复杂度一样高。通过构造一个规则来反驳这个猜想。实例复杂度为Kolmogorov复杂度对数的非递归集。该界限在加法常数之前是最佳的。在另一种极端情况下，对于许多类的完整集（例如弱真实表完整（wtt-完整）和Q-完整集）建立了猜想。但是，有一个图灵完备集会失败。 [参考：16]

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号