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 P0 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} as the minimal extension of T proving for some algorithm that it decides P0 as fast as any algorithm B with the property that T proves that B decides P0. Here, ConT 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 等数据库收录! |
|