Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)

DOI10.4230/LIPICS.CSL.2012.9zbMATH Open1252.03131OpenAlexW2244997347MaRDI QIDQ4649532FDOQ4649532

Authors: Stephen Cook 

Publication date: 22 November 2012

Full work available at URL: https://doi.org/10.4230/LIPIcs.CSL.2012.9

Recommendations

• Complexity of propositional proofs (invited talk)
• scientific article; zbMATH DE number 7650818
• scientific article; zbMATH DE number 3896918
• scientific article; zbMATH DE number 2196512
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• A note on the complexity of classical and intuitionistic proofs
• scientific article; zbMATH DE number 1342249
• A finite-model-theoretic view on propositional proof complexity
• On complete problems, relativizations and logics for complexity classes
• Relativization and interactive proof systems in parameterized complexity theory

zbMATH Keywords

complexity classespropositional proof systemsweak formal theories

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

This page was built for publication: Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4649532)