A fast consistency prover is a consistent polytime axiomatized theory that has short proofs of the finite consistency statements of any other polytime axiomatized theory. Krajíček and Pudlák have proved that the existence of an optimal propositional proof system is equivalent to the existence of a fast consistency prover. It is an easy observation that NP = coNP implies the existence of a fast consistency prover. The reverse implication is an open question. In this paper we define the notion of an unlikely fast consistency prover and prove that its existence is equivalent to
NP = coNP. Next it is proved that fast consistency provers do not exist if one considers RE axiomatized theories rather than theories with an axiom set that is recognizable in polynomial time.
Publié le : 2007-07-14
Classification:
computational complexity,
bounded arithmetic,
length of proofs,
03B70,
68Q15
@article{1187031410,
author = {Joosten, Joost J.},
title = {Propositional Proof Systems and Fast Consistency Provers},
journal = {Notre Dame J. Formal Logic},
volume = {48},
number = {1},
year = {2007},
pages = { 381-398},
language = {en},
url = {http://dml.mathdoc.fr/item/1187031410}
}
Joosten, Joost J. Propositional Proof Systems and Fast Consistency Provers. Notre Dame J. Formal Logic, Tome 48 (2007) no. 1, pp. 381-398. http://gdmltest.u-ga.fr/item/1187031410/