Automating algebraic proof systems is NP-hard

DOI10.1145/3406325.3451080OpenAlexW3171867428WikidataQ130967589 ScholiaQ130967589MaRDI QIDQ6086995

Author name not available (Why is that?)

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3406325.3451080

zbMATH Keywords

lower boundsalgebraic proof systemsproof complexitypigeonhole principleautomatability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Proof complexity and the binary encoding of combinatorial principles ⋮ Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024

Recommendations

• On the automatizability of resolution and related propositional proof systems 👍 👎
• Automatic Proof Generation in Kleene Algebra 👍 👎
• Proof simplification and automated theorem proving 👍 👎
• Hard Instances of Algorithms and Proof Systems 👍 👎
• Hard Instances of Algorithms and Proof Systems 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Automating algebraic proof systems is NP-hard

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