Easy problems are sometimes hard

DOI10.1016/0004-3702(94)90109-0zbMath0824.68107OpenAlexW2137154807MaRDI QIDQ1342226

Toby Walsh, Ian Philip Gent

Publication date: 11 January 1995

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

Full work available at URL: https://doi.org/10.1016/0004-3702(94)90109-0

zbMATH Keywords

satisfiability

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

The hardest constraint problems: A double phase transition ⋮ Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study ⋮ Easy problems are sometimes hard ⋮ Implementing semantic merging operators using binary decision diagrams ⋮ Statistical regimes across constrainedness regions ⋮ The impact of search heuristics on heavy-tailed behaviour ⋮ The state of SAT ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ Phase transitions and the search problem ⋮ Generating hard satisfiability problems ⋮ Experimental results on the crossover point in random 3-SAT ⋮ The satisfiability constraint gap ⋮ An empirical study of phase transitions in binary constraint satisfaction problems ⋮ Refining the phase transition in combinatorial search ⋮ Problem structure heuristics and scaling behavior for genetic algorithms ⋮ The TSP phase transition ⋮ Is computational complexity a barrier to manipulation? ⋮ 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 ⋮ Algorithms for Effective Argumentation in Classical Propositional Logic: A Connection Graph Approach ⋮ A generative power-law search tree model ⋮ Linear programs for constraint satisfaction problems ⋮ Problem difficulty for tabu search in job-shop scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The hardest constraint problems: A double phase transition
• Easy problems are sometimes hard
• Branch-and-cut solution of inference problems in propositional logic
• Solving propositional satisfiability problems
• The Pure Literal Rule and Polynomial Average Time
• A Computing Procedure for Quantification Theory