2026-04-17T17:09:07Zhttps://recercat.cat/oai/request

oai:recercat.cat:2072/1697362026-01-15T12:56:04Zcom_2072_199267com_2072_4427col_2072_199862

Consistency and optimality Chen, Yijia Flum, Jörg Müller, Moritz Centre de Recerca Matemàtica Conjunts, Teoria de Complexitat de càlcul 510 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. 2011 info:eu-repo/semantics/preprint http://hdl.handle.net/2072/169736 eng Prepublicacions del Centre de Recerca Matemàtica;1014 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/) 11 187164 bytes application/pdf application/pdf Centre de Recerca Matemàtica RECERCAT (Dipòsit de la Recerca de Catalunya)