scientific article; zbMATH DE number 1114014

MaRDI QIDQ4375783zbMATH OpenFDO

Authors Jeremy Avigad

Publication date 8 July 1998

zbMATH Keywords

propositional proof systemFrege systemcombinatorial tautologies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 806744
• The Complexity of Propositional Proofs with the Substitution Rule
• scientific article; zbMATH DE number 1500525
• scientific article; zbMATH DE number 1179974

Cited in

(7)

• Combinatorial versus decision-theoretic components of impossibility theorems
• Tautologies from pseudo-random generators
• Generating hard tautologies using predicate logic and the symmetric group
• On the computational complexity of finding hard tautologies
• Propositional proofs in Frege and extended Frege systems (abstract)
• Short proofs of the Kneser-Lovász coloring principle
• The provably total NP search problems of weak second order bounded arithmetic

This page was built for publication:

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