Consistency, optimality, and incompleteness

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.