The satisfiability constraint gap

DOI10.1016/0004-3702(95)00047-XOpenAlexW2050430186MaRDI QIDQ2674178

Toby Walsh, Ian Philip Gent

Publication date: 22 September 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(95)00047-x

zbMATH Keywords

constraint propagationsatisfiabilityhard problemssearch phase transitions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

Implicates and prime implicates in random 3-SAT ⋮ Frozen development in graph coloring ⋮ Backtracking algorithms for disjunctions of temporal constraints ⋮ Complexity-theoretic models of phase transitions in search problems

Cites Work

• Unnamed Item
• Unnamed Item
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The hardest constraint problems: A double phase transition
• Exploiting the deep structure of constraint problems
• Easy problems are sometimes hard
• Branch-and-cut solution of inference problems in propositional logic
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: The satisfiability constraint gap