Generating hard satisfiability problems
From MaRDI portal
Publication:2674174
DOI10.1016/0004-3702(95)00045-3WikidataQ56039657 ScholiaQ56039657MaRDI QIDQ2674174
Hector J. Levesque, Bart Selman, David G. Mitchell
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)00045-3
68Q25: Analysis of algorithms and problem complexity
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Algorithms for Effective Argumentation in Classical Propositional Logic: A Connection Graph Approach, A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses, Rigorous results for random (\(2+p)\)-SAT, Results related to threshold phenomena research in satisfiability: Lower bounds, A competitive and cooperative approach to propositional satisfiability, Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes, Remote Agent: to boldly go where no AI system has gone before, Generalized satisfiability problems: Minimal elements and phase transitions., How to fake an RSA signature by encoding modular root finding as a SAT problem, Experimental complexity analysis of continuous constraint satisfaction problems., Backtracking algorithms for disjunctions of temporal constraints, Nagging: A scalable fault-tolerant paradigm for distributed search, On SAT instance classes and a method for reliable performance experiments with SAT solvers, A sharp threshold in proof complexity yields lower bounds for satisfiability search, Implementing semantic merging operators using binary decision diagrams, Partition-based logical reasoning for first-order and propositional theories, Compiling problem specifications into SAT, A new constraint test-case generator and the importance of hybrid optimizers, On the complexity of unfrozen problems, Phase transitions of PP-complete satisfiability problems, Hierarchical Hardness Models for SAT
Uses Software
