scientific article; zbMATH DE number 1114014

zbMATH Open0891.03024MaRDI QIDQ4375783FDOQ4375783

Authors: Jeremy Avigad 

Publication date: 8 July 1998

Title of this publication is not available (Why is that?)

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

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)

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)