On sufficient conditions for unsatisfiability of random formulas
From MaRDI portal
Publication:5501191
DOI10.1145/972639.972645zbMath1316.68055OpenAlexW2123581574MaRDI QIDQ5501191
Publication date: 1 August 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/972639.972645
Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Classical propositional logic (03B05) Logic programming (68N17) Complexity of proofs (03F20) Descriptive complexity and finite models (68Q19)
Related Items (8)
On digraph coloring problems and treewidth duality ⋮ Constructing Hard Examples for Graph Isomorphism ⋮ A combinatorial characterization of resolution width ⋮ Space proof complexity for random 3-CNFs ⋮ A Framework for Space Complexity in Algebraic Proof Systems ⋮ Definable Inapproximability: New Challenges for Duplicator ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ Unnamed Item
This page was built for publication: On sufficient conditions for unsatisfiability of random formulas
