The complexity of propositional proofs
Segerlind, Nathan
Bull. Symbolic Logic, Tome 13 (2007) no. 3, p. 417-481 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.
Publié le : 2007-12-15
Classification:  
@article{1203350879,
     author = {Segerlind, Nathan},
     title = {The complexity of propositional proofs},
     journal = {Bull. Symbolic Logic},
     volume = {13},
     number = {3},
     year = {2007},
     pages = { 417-481},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1203350879}
}

Segerlind, Nathan. The complexity of propositional proofs. Bull. Symbolic Logic, Tome 13 (2007) no. 3, pp.  417-481. http://gdmltest.u-ga.fr/item/1203350879/