首页> 外文期刊>Chicago Journal of Theoretical Computer Science >Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic
【24h】

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

机译:Kolmogorov的复杂性,电路和算术形式理论的强度

获取原文
获取外文期刊封面目录资料

摘要

Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems $cal C$ defined in terms of polynomial-time truth-table reducibility to $RK$ (the set of Kolmogorov-random strings) that lies between $BPP$ and $PSPACE$. The results in this paper were obtained, as part of an investigation of whether this upper bound can be improved, to show $$ BPP subseteq {cal C} subseteq PSPACE cap Ppoly. quadquadquad(*)$$ In fact, we conjecture that ${cal C} = BPP = Polytime$, and we close this paper with a discussion of the possibility this might be an avenue for trying to prove the equality of $BPP$ and $Polytime$. In this paper, we present a collection of true statements in the language of arithmetic, (each provable in ZF) and show that if these statements can be proved in certain extensions of Peano arithmetic ($PA$), then (*) holds. Although it was subsequently proved (by Allender, Buhrman, Friedman and Loff) that infinitely many of these statements are, in fact, independent of those extensions of $PA$, we present these results in the hope that related ideas may yet contribute to a proof of ${cal C} = BPP$, and because this work did serve as a springboard for subsequent work in the area.
机译:是否可以根据对(不确定的)Kolmogorov随机字符串集的有效可归约性来表征复杂度类?尽管这似乎不太可能,但最近有一系列论文提供了证明可能是事实。尤其是,已知存在一类问题$ cal C $,是根据多项式时间真值表对$ RK $(Kolmogorov随机字符串的集合)的可约约性定义的,介于$ BPP $和$ PSPACE $。作为对是否可以提高此上限的研究的一部分,获得了本文的结果,以显示$$ BPP subseteq { cal C} subseteq PSPACE cap Ppoly。 quad quad quad(*)$$实际上,我们推测$ { cal C} = BPP = Polytime $,并且在本文结尾处讨论了这可能是尝试证明$ BPP $和$ Polytime $相等。在本文中,我们用算术语言(每一个都在ZF中证明)提供了一组真实的语句,并表明,如果可以用Peano算术的某些扩展($ PA $)证明这些语句,则(*)成立。尽管随后(由Allender,Buhrman,Friedman和Loff证明)这些语句中有许多实际上与$ PA $的扩展无关,但我们提出这些结果是希望相关的思想可能对$ { cal C} = BPP $的证明,并且因为这项工作确实是该地区后续工作的跳板。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号