Graduate studies at Western
Bulletin of Symbolic Logic 13 (4):417-481 (2007)
|Abstract||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|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Andrzej Wiśniewski, Guido Vanackere & Dorota Leszczyńska (2005). Socratic Proofs and Paraconsistency: A Case Study. Studia Logica 80 (2-3):431 - 466.
Alasdair Urquhart (1995). The Complexity of Propositional Proofs. Bulletin of Symbolic Logic 1 (4):425-467.
Andrzej Wiśniewski (2004). Socratic Proofs. Journal of Philosophical Logic 33 (3):299-326.
Merlijn Sevenster (2006). On the Computational Consequences of Independence in Propositional Logic. Synthese 149 (2):257 - 283.
Jan Krajíček (1997). Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic. Journal of Symbolic Logic 62 (2):457-486.
Jan Krajíček (2004). Implicit Proofs. Journal of Symbolic Logic 69 (2):387 - 397.
Samuel R. Buss (1987). Polynomial Size Proofs of the Propositional Pigeonhole Principle. Journal of Symbolic Logic 52 (4):916-927.
Maria Bonet, Toniann Pitassi & Ran Raz (1997). Lower Bounds for Cutting Planes Proofs with Small Coefficients. Journal of Symbolic Logic 62 (3):708-728.
Jan Krajíček & Pavel Pudlák (1989). Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations. Journal of Symbolic Logic 54 (3):1063-1079.
Jan Krajíček (1995). Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press.
Added to index2009-02-05
Total downloads5 ( #170,097 of 739,304 )
Recent downloads (6 months)0
How can I increase my downloads?