dc.contributor
Centre de Recerca Matemàtica
dc.contributor.author
Chen, Yijia
dc.contributor.author
Flum, Jörg
dc.contributor.author
Müller, Moritz
dc.date.accessioned
2011-09-21T07:40:20Z
dc.date.accessioned
2024-09-19T13:21:18Z
dc.date.available
2011-09-21T07:40:20Z
dc.date.available
2024-09-19T13:21:18Z
dc.identifier.uri
http://hdl.handle.net/2072/169736
dc.description.abstract
Assume that the problem Qo is not solvable in polynomial time. For theories T containing a sufficiently rich part of true arithmetic we characterize T U {ConT} as the minimal extension of T proving for some algorithm that it decides Qo as fast as any algorithm B with the property that T proves that B decides Qo. Here, ConT claims the consistency of T. Moreover, we characterize problems with an optimal algorithm in terms of arithmetical theories.
cat
dc.format.extent
187164 bytes
dc.format.mimetype
application/pdf
dc.publisher
Centre de Recerca Matemàtica
ca
dc.relation.ispartofseries
Prepublicacions del Centre de Recerca Matemàtica;1014
dc.rights
Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús (http://creativecommons.org/licenses/by-nc-nd/2.5/es/)
cat
dc.subject.other
Conjunts, Teoria de
ca
dc.subject.other
Complexitat de càlcul
ca
dc.title
Consistency and optimality
ca
dc.type
info:eu-repo/semantics/preprint
ca
