Experimental results on the crossover point in random 3-SAT
From MaRDI portal
Publication:2674177
DOI10.1016/0004-3702(95)00046-1OpenAlexW2155218845WikidataQ126789311 ScholiaQ126789311MaRDI QIDQ2674177
Larry D. Auton, James M. Crawford
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)00046-1
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (29)
Variations and extension of the convex-concave procedure ⋮ Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ A novel algorithm for Max Sat calling MOCE to order ⋮ On threshold properties of \(k\)-SAT: An additive viewpoint ⋮ Modelling and solving temporal reasoning as propositional satisfiability ⋮ Planning as satisfiability: heuristics ⋮ Implicates and prime implicates in random 3-SAT ⋮ The TSP phase transition ⋮ Generating Difficult CNF Instances in Unexplored Constrainedness Regions ⋮ Generating random instances of weighted model counting. An empirical analysis with varying primal treewidth ⋮ CHAMP: a multipass algorithm for Max Sat based on saver variables ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ How to fake an RSA signature by encoding modular root finding as a SAT problem ⋮ On the limit of branching rules for hard random unsatisfiable 3-SAT ⋮ SAT problems with chains of dependent variables ⋮ Effective use of Boolean satisfiability procedures in the formal verification of superscalar and VLIW microprocessors. ⋮ A general system for heuristic minimization of convex functions over non-convex sets ⋮ A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses ⋮ On the complexity of \(k\)-SAT ⋮ Upper bounds on the satisfiability threshold ⋮ Frozen development in graph coloring ⋮ New models for generating hard random Boolean formulas and disjunctive logic programs ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Backtracking algorithms for disjunctions of temporal constraints ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ An efficient local search method for random 3-satisfiability ⋮ Extending and implementing the stable model semantics ⋮ On market-inspired approaches to propositional satisfiability
Cites Work
- The hardest constraint problems: A double phase transition
- Easy problems are sometimes hard
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Many hard examples for resolution
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- A machine program for theorem-proving
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Experimental results on the crossover point in random 3-SAT
