一致性最优性和不完整性

假设问题P-0在多项式时间内无法解决。 设T为一阶理论,其中包含真算术的足够丰富的部分。 我们将TU {Con(T)}表征为T的最小扩展,证明它对某种算法的决定P-0的速度与任何算法B一样快,并且具有T证明B决定P-0的性质。 在这里,Con(T)声称T的一致性。作为副产品,我们获得了Godel第二不完全性定理的一个版本。 此外,我们根据算术理论来描述使用最佳算法的问题。