Typical case complexity of satisfiability algorithms and the threshold phenomenon
From MaRDI portal
Publication:2581549
DOI10.1016/j.dam.2005.05.008zbMath1101.68838OpenAlexW1983259451MaRDI QIDQ2581549
Publication date: 10 January 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2005.05.008
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Near optimal seperation of tree-like and general resolution
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- On finding solutions for extended Horn formulas
- A threshold for unsatisfiability
- Average time analyses of simplified Davis-Putnam procedures
- A simplified NP-complete satisfiability problem
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- The intractability of resolution
- Probabilistic performance of a heurisic for the satisfiability problem
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Approximation algorithms for combinatorial problems
- Recognition of \(q\)-Horn formulae in linear time
- Generalized satisfiability problems: Minimal elements and phase transitions.
- Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Investigations on autark assignments
- A perspective on certain polynomial-time solvable classes of satisfiability
- Differential equations for random processes and random graphs
- The scaling window of the 2-SAT transition
- The complexity of the matrix eigenproblem
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
- Selecting Complementary Pairs of Literals
- Many hard examples for resolution
- The threshold for random k-SAT is 2 k (ln 2 - O(k))
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Hard examples for resolution
- Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms
- Renaming a Set of Clauses as a Horn Set
- On Resolution with Clauses of Bounded Size
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- A Complexity Index for Satisfiability Problems
- Extended Horn sets in propositional logic
- Probe Order Backtracking
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Short proofs are narrow—resolution made simple
- On Representatives of Subsets
- Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
- Tail bounds for occupancy and the satisfiability threshold conjecture
- On Random 3-sat
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Determining computational complexity from characteristic ‘phase transitions’
- A Machine-Oriented Logic Based on the Resolution Principle
- A machine program for theorem-proving
- Random constraint satisfaction: A more accurate picture
- Rigorous results for random (\(2+p)\)-SAT
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Lower bounds for random 3-SAT via differential equations
- Upper bounds on the satisfiability threshold
