首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Consistency,optimality, and incompleteness
Authors:Yijia Chen  Jörg Flum  Moritz Müller
Institution:1. Shanghai Jiaotong University, China;2. Albert-Ludwigs-Universität Freiburg, Germany;3. Kurt Gödel Research Center, University of Vienna, Austria
Abstract:Assume that the problem P0P0 is not solvable in polynomial time. Let T   be a first-order theory containing a sufficiently rich part of true arithmetic. We characterize T∪{ConT}T{ConT} as the minimal extension of T   proving for some algorithm that it decides P0P0 as fast as any algorithm BB with the property that T   proves that BB decides P0P0. Here, ConTConT claims the consistency of T. As a byproduct, we obtain a version of Gödel?s Second Incompleteness Theorem. Moreover, we characterize problems with an optimal algorithm in terms of arithmetical theories.
Keywords:03B30  03E35  03F30  03F40
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号