Complexity of propositional proofs under a promise

DOI10.1145/1740582.1740586zbMath1351.03057arXiv0707.4255OpenAlexW2153912760MaRDI QIDQ2946606

Nachum Dershowitz, Iddo Tzameret

Publication date: 17 September 2015

Published in: ACM Transactions on Computational Logic, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0707.4255

zbMATH Keywords

resolutionproof complexitypromise problemspropositional proof complexityrandom 3CNF

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of proofs (03F20)

Related Items (1)

Collapsing modular counting in bounded arithmetic and constant depth propositional proofs

This page was built for publication: Complexity of propositional proofs under a promise