Many hard examples in exact phase transitions
From MaRDI portal
Publication:2368999
DOI10.1016/j.tcs.2006.01.001zbMath1088.68163OpenAlexW2085826829MaRDI QIDQ2368999
Publication date: 28 April 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2006.01.001
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)
Related Items (28)
Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden ⋮ Super Solutions of Random Instances of Satisfiability ⋮ PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP ⋮ Computing the metric dimension of graphs by genetic algorithms ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY ⋮ An upper (lower) bound for Max (Min) CSP ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ Threshold behaviors of a random constraint satisfaction problem with exact phase transitions ⋮ Complete Boolean satisfiability solving algorithms based on local search ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ Fractional Edge Cover Number of Model RB ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability ⋮ A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming ⋮ On exponential time lower bound of Knapsack under backtracking ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ On the Minimal Constraint Satisfaction Problem: Complexity and Generation ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ Computing minimal doubly resolving sets of graphs ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Unnamed Item ⋮ Large hypertree width for sparse random hypergraphs ⋮ On the constraint length of random \(k\)-CSP
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- An algorithm for finding Hamilton paths and cycles in random graphs
- A probabilistic analysis of randomly generated binary constraint satisfaction problems.
- On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
- The 3-XORSAT threshold.
- A sharp threshold for a random constraint satisfaction problem
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- The Efficiency of Resolution and Davis--Putnam Procedures
- The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
- Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
- Many hard examples for resolution
- The Resolution Complexity of Random Constraint Satisfaction Problems
- Sharp thresholds of graph properties, and the $k$-sat problem
- Short proofs are narrow—resolution made simple
- Models for Random Constraint Satisfaction Problems
- Determining computational complexity from characteristic ‘phase transitions’
- Scaling and universality in continuous length combinatorial optimization
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
- Random constraint satisfaction: A more accurate picture
- Random constraint satisfaction: Flaws and structure
- Rigorous results for random (\(2+p)\)-SAT
- Constructing an asymptotic phase transition in random binary constraint satisfaction problems
This page was built for publication: Many hard examples in exact phase transitions
