Super solutions of random instances of satisfiability
DOI10.1007/978-3-319-19647-3_29zbMATH Open1356.68112OpenAlexW2407566837MaRDI QIDQ3452579FDOQ3452579
Authors: Peng Zhang, Yong Gao 
Publication date: 12 November 2015
Published in: Frontiers in Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-19647-3_29
Recommendations
- A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
- Super solutions of random \((3 + p)\)-SAT
- On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
- A sharp threshold for a random constraint satisfaction problem
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Frozen development in graph coloring
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Many hard examples in exact phase transitions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- The threshold for random k-SAT is 2 k (ln 2 - O(k))
Cited In (6)
- Super solutions of random \((3 + p)\)-SAT
- On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
- On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT
- Expected number of locally maximal solutions for random Boolean CSPs
- The super-replication problem via probabilistic methods
- A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
This page was built for publication: Super solutions of random instances of satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452579)
