Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations

Krajicek, Jan; Pudlak, Pavel

J. Symbolic Logic, Tome 54 (1989) no. 1, p. 1063-1079 / Harvested from Project Euclid

Résumé

We consider the problem about the length of proofs of the sentences $\operatorname{Con}_S(\underline{n})$ saying that there is no proof of contradiction in $S$ whose length is $\leq n$. We show the relation of this problem to some problems about propositional proof systems.

Publié le : 1989-09-14
Classification:

@article{1183743040,
     author = {Krajicek, Jan and Pudlak, Pavel},
     title = {Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations},
     journal = {J. Symbolic Logic},
     volume = {54},
     number = {1},
     year = {1989},
     pages = { 1063-1079},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183743040}
}

Krajicek, Jan; Pudlak, Pavel. Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations. J. Symbolic Logic, Tome 54 (1989) no. 1, pp.  1063-1079. http://gdmltest.u-ga.fr/item/1183743040/