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

DOI10.4230/LIPICS.CSL.2012.9MaRDI QIDQ4649532zbMATH OpenOpenAlexFDO

Authors Stephen Cook

Publication date 22 November 2012

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

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)

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

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)