Many hard examples for resolution

DOI10.1145/48014.48016MaRDI QIDQ3496310zbMATH OpenOpenAlexWikidataFDO

Authors Vašek Chvátal, Endre Szemerédi

Publication date 1988

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

satisfiabilityresolution proofunsatisfiabilitycomplexity of proof procedures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35)

Recommendations

• On Random 3-sat
• scientific article; zbMATH DE number 1775444
• Random resolution refutations
• A sharp threshold in proof complexity
• The Resolution Complexity of Random Constraint Satisfaction Problems

Cited in

(only showing first 100 items - show all)

• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT
• Almost all graphs with 1.44n edges are 3-colorable
• Resolution lower bounds for the weak functional pigeonhole principle.
• A spectral technique for random satisfiable 3CNF formulas
• A general model and thresholds for random constraint satisfaction problems
• The state of SAT
• Tseitin's formulas revisited
• Reflections on Proof Complexity and Counting Principles
• Lower bounds for \(k\)-DNF resolution on random 3-CNFs
• The probabilistic analysis of a greedy satisfiability algorithm
• Many hard examples in exact phase transitions
• An improved upper bound on the non-3-colourability threshold
• A feasibly constructive lower bound for resolution proofs
• Construction of expanders and superconcentrators using Kolmogorov complexity
• Upper bounds on the satisfiability threshold
• Cumulative space in black-white pebbling and resolution
• Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random \(k\)-SAT
• Captain Jack: new variable selection heuristics in local search for SAT
• Simplified lower bounds for propositional proofs
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• Clause trees: A tool for understanding and implementing resolution in automated reasoning
• On hard instances
• On the relation among answer set solvers
• An average case analysis of a resolution principle algorithm in mechanical theorem proving.
• Some computational aspects of DISTANCE SAT
• When does the giant component bring unsatisfiability?
• Towards NP-P via proof complexity and search
• An exponential lower bound for the size of monotone real circuits
• Implicates and prime implicates in random 3-SAT
• On the structure of some classes of minimal unsatisfiable formulas
• Complete on average Boolean satisfiability
• Spines of random constraint satisfaction problems: definition and connection with computational complexity
• Short propositional refutations for dense random 3CNF formulas
• The \(Multi\)-SAT algorithm
• Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
• A combinatorial characterization of resolution width
• Meta-resolution: An algorithmic formalisation
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• On the relations between SAT and CSP enumerative algorithms
• Unrestricted resolution versus N-resolution
• Counting truth assignments of formulas of bounded tree-width or clique-width
• From small space to small width in resolution
• An Introduction to Lower Bounds on Resolution Proof Systems
• Hard random 3-SAT problems and the Davis-Putnam procedure
• A perspective on certain polynomial-time solvable classes of satisfiability
• Propositional proof complexity
• A lower bound for tree resolution
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Davis-Putnam resolution versus unrestricted resolution
• The Complexity of Propositional Proofs
• Mutilated chessboard problem is exponentially hard for resolution
• A combinatorial characterization of treelike resolution space
• Limitations of restricted branching in clause learning
• Generating hard satisfiability problems
• Experimental results on the crossover point in random 3-SAT
• The symmetry rule in propositional logic
• Probabilistic bounds and algorithms for the maximum satisfiability problem
• Supercritical space-width trade-offs for resolution
• Frozen development in graph coloring
• An efficient local search method for random 3-satisfiability
• Parameterized complexity of DPLL search procedures
• A threshold for unsatisfiability
• On good algorithms for determining unsatisfiability of propositional formulas
• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• The scaling window of the 2-SAT transition
• On the hardness of SAT with community structure
• Regular random \(k\)-SAT: Properties of balanced formulas
• Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
• Space bounds for resolution
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• Width versus size in resolution proofs
• Testing satisfiability of CNF formulas by computing a stable set of points
• An Upper Bound on the Space Complexity of Random Formulae in Resolution
• Consistency, acyclicity, and positive Semirings
• Solving non-uniform planted and filtered random SAT formulas greedily
• scientific article; zbMATH DE number 408796 (Why is no real title available?)
• A framework for space complexity in algebraic proof systems
• Reasoning with propositional logic: from SAT solvers to knowledge compilation
• Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
• DP-Complete Problems Derived from Extremal NP-Complete Properties
• scientific article; zbMATH DE number 7561756 (Why is no real title available?)
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
• Trade-offs between time and memory in a tighter model of CDCL SAT solvers
• On minimal unsatisfiability and time-space trade-offs for \(k\)-DNF resolution
• The solution space geometry of random linear equations
• Irreducible subcube partitions
• Witnesses for Answer Sets of Logic Programs
• Narrow proofs may be maximally long
• Finding the hardest formulas for resolution
• Space Complexity in Polynomial Calculus
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• Graph decompositions and tree automata in reasoning with uncertainty
• Random resolution refutations
• A tutorial on time and space bounds in tree-like resolution
• Polarised random \(k\)-SAT
• Space proof complexity for random 3-CNFs

This page was built for publication: Many hard examples for resolution

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