Consistency, optimality, and incompleteness
Consistency, optimality, and incompleteness
复制标题
一致性、最优性和不完整性
DOI：
10.1016/j.apal.2013.06.009
复制
发表时间：
2013-12
影响因子：
0.8
通讯作者：
Moritz Mueller
中科院分区：
文献类型：
--
作者：
Yijia Chen;Joerg Flum;Moritz Mueller
假设问题P0在多项式时间内是不可解的.设T是一阶理论，它包含了真算术的足够丰富的部分。我们把T ∈ {Con T}刻画为T证明的最小扩张，T证明了某个算法可以和任何算法B一样快地决定P0，并且T证明了B决定P0.这里，Con T要求T的一致性。作为副产品，我们得到了哥德尔第二不完全性定理的一个版本。此外，我们刻画了问题的最优算法的算术理论。
Assume that the problem P 0 is not solvable in polynomial time. Let T be a first-order theory containing a sufficiently rich part of true arithmetic. We characterize T∪{Con T} as the minimal extension of T proving for some algorithm that it decides P 0 as fast as any algorithm B with the property that T proves that B decides P 0. Here, Con T 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.
登录
查看更多内容
DOI：
10.1145/800105.803412
发表时间：
1977-05
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
J. Hartmanis
通讯作者：
J. Hartmanis
DOI：
--
发表时间：
1974
期刊：
--
影响因子：
--
作者：
L. Stockmeyer
通讯作者：
L. Stockmeyer
影响因子：
0.6
作者：
J. Krajícek;P. Pudlák
通讯作者：
J. Krajícek;P. Pudlák
DOI：
10.1016/s0304-3975(01)00155-4
发表时间：
2002-10
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Zenon Sadowski
通讯作者：
Zenon Sadowski
DOI：
10.1007/3-540-49116-3_51
发表时间：
1999-03
期刊：
--
影响因子：
--
作者：
J. Messner
通讯作者：
J. Messner