Consistency, optimality, and incompleteness

Annals of Pure and Applied Logic 164 (12):1224-1235 (2013)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 80,119

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Herbrand consistency of some arithmetical theories.Saeed Salehi - 2012 - Journal of Symbolic Logic 77 (3):807-827.
Optimality modeling in a suboptimal world.Angela Potochnik - 2009 - Biology and Philosophy 24 (2):183-197.
On the philosophical relevance of Gödel's incompleteness theorems.Panu Raatikainen - 2005 - Revue Internationale de Philosophie 59 (4):513-534.
On Herbrand consistency in weak arithmetic.Zofia Adamowicz & Paweł Zbierski - 2001 - Archive for Mathematical Logic 40 (6):399-413.
Heterologicality and Incompleteness.Cezary Cieśliński - 2002 - Mathematical Logic Quarterly 48 (1):105-110.


Added to PP

38 (#321,223)

6 months
1 (#477,905)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations