Space complexity in propositional calculus

DOI10.1145/335305.335347MaRDI QIDQ3192004zbMATHOpenAlexFDO

Authors Michael Alekhnovich, Eli Ben-Sasson, A. Wigderson, Alexander Razborov

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Recommendations

• Space Complexity in Propositional Calculus
• Space complexity in polynomial calculus
• Space bounds for resolution
• From small space to small width in resolution
• scientific article; zbMATH DE number 1424047

Cited in

(10)

• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• scientific article; zbMATH DE number 6482141 (Why is no real title available?)
• On the complexity of resolution with bounded conjunctions
• A framework for space complexity in algebraic proof systems
• Computer Science Logic
• scientific article; zbMATH DE number 2081098 (Why is no real title available?)
• Pseudo-partitions, transversality and locality, a combinatorial characterization for the space measure in algebraic proof systems
• Space Complexity in Propositional Calculus
• Space bounds for resolution
• Space complexity of random formulae in resolution

This page was built for publication: Space complexity in propositional calculus

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