The power of the binary value principle

DOI10.1016/J.APAL.2025.103614MaRDI QIDQ6952562zbMATH OpenFDO

Authors Yaroslav Alekseev, Edward A. Hirsch

Publication date 27 July 2025

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.APAL.2025.103614

zbMATH Keywords

extension rulepolynomial calculusproof complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• A lower bound for polynomial calculus with extension rule
• Algebraic proof systems over formulas.
• Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
• First-order reasoning and efficient semi-algebraic proofs
• scientific article; zbMATH DE number 5161489 (Why is no real title available?)
• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 1916823 (Why is no real title available?)
• scientific article; zbMATH DE number 1390276 (Why is no real title available?)
• scientific article; zbMATH DE number 3325539 (Why is no real title available?)
• Polynomial size proofs of the propositional pigeonhole principle
• Resolution with counting: dag-like lower bounds and different moduli
• Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
• The relative efficiency of propositional proof systems
• The surprising power of constant depth algebraic proofs

This page was built for publication: The power of the binary value principle

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