The polynomial bounds of proof complexity in Frege systems

MaRDI QIDQ5391544zbMATH OpenFDO

Authors S. R. Aleksanyan, A. A. Chubaryan

Publication date 6 April 2011

Full work available at URL https://eudml.org/doc/233542, http://www.emis.de/journals/SMZ/2009/02/243.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

determinative conjunctdeterminative setFrege systemhard-determinable formulaproof complexity

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• scientific article; zbMATH DE number 6387509
• Propositional proofs in Frege and extended Frege systems (abstract)
• The Complexity of Propositional Proofs
• scientific article; zbMATH DE number 65760
• Polynomial size proofs of the propositional pigeonhole principle

Cited in

(8)

• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• Hard examples for the bounded depth Frege proof system
• A bounded arithmetic AID for Frege systems
• Inference of bounded L systems with polymorphic P systems
• Upper bounds on complexity of Frege proofs with limited use of certain schemata
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• The properties of determinative disjunctive normal forms and systems based on them
• Polynomially and superexponentially shorter proofs in fragments of arithmetic

This page was built for publication: The polynomial bounds of proof complexity in Frege systems

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