Space complexity of random formulae in resolution
DOI10.1002/rsa.10089zbMath1048.03046MaRDI QIDQ4417005
Publication date: 6 August 2003
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.10089
lower bounds on the clause space; matching games on bipartite graphs; space complexity of refuting unsatisfiable random formulas; treelike resolution refutations
91A43: Games involving graphs
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
03B35: Mechanization of proofs and logical operations
03D15: Complexity of computation (including implicit computational complexity)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
Cites Work