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)

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

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)