Space complexity in propositional calculus

DOI10.1145/335305.335347zbMATH Open1296.03032OpenAlexW2097746739MaRDI QIDQ3192004FDOQ3192004

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

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

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

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Cited In (8)

• On the complexity of resolution with bounded conjunctions
• Title not available (Why is that?)
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Title not available (Why is that?)
• Space Complexity in Propositional Calculus
• A framework for space complexity in algebraic proof systems
• Space complexity of random formulae in resolution
• Space bounds for 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)