The satisfiability constraint gap
From MaRDI portal
Publication:2674178
DOI10.1016/0004-3702(95)00047-XOpenAlexW2050430186MaRDI QIDQ2674178
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
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