The satisfiability constraint gap

DOI10.1016/0004-3702(95)00047-XMaRDI QIDQ2674178zbMATH OpenOpenAlexFDO

Authors Toby Walsh, Ian P. 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 propagationhard problemssatisfiabilitysearch phase transitions

Mathematics Subject Classification ID

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

Recommendations

• The complexity of satisfiability problems
• Artificial Intelligence: Methodology, Systems, and Applications
• The complexity of constraint satisfaction revisited
• The approximability of constraint satisfaction problems
• The logic of constraint satisfaction
• Bridging constraint satisfaction and Boolean satisfiability
• scientific article; zbMATH DE number 496040
• scientific article; zbMATH DE number 1234562
• Methods and Applications of Artificial Intelligence
• Constraint satisfaction from a deductive viewpoint

Cites work

• A Computing Procedure for Quantification Theory
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A machine program for theorem-proving
• Branch-and-cut solution of inference problems in propositional logic
• Easy problems are sometimes hard
• Exploiting the deep structure of constraint problems
• Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 956858 (Why is no real title available?)
• The hardest constraint problems: A double phase transition

Cited in

(16)

• Easy problems are sometimes hard
• Backtracking algorithms for disjunctions of temporal constraints
• Complexity-theoretic models of phase transitions in search problems
• Experimental results on the crossover point in random 3-SAT
• An empirical study of phase transitions in binary constraint satisfaction problems
• Refining the phase transition in combinatorial search
• Locating the phase transition in binary constraint satisfaction problems
• Hard random 3-SAT problems and the Davis-Putnam procedure
• Implicates and prime implicates in random 3-SAT
• scientific article; zbMATH DE number 3954272 (Why is no real title available?)
• scientific article; zbMATH DE number 1149446 (Why is no real title available?)
• scientific article; zbMATH DE number 1954174 (Why is no real title available?)
• scientific article; zbMATH DE number 6861969 (Why is no real title available?)
• A threshold for unsatisfiability
• scientific article; zbMATH DE number 956862 (Why is no real title available?)
• Frozen development in graph coloring

This page was built for publication: The satisfiability constraint gap

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