Super solutions of random instances of satisfiability

DOI10.1007/978-3-319-19647-3_29MaRDI QIDQ3452579zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 5547880 (Why is no real title available?)
• scientific article; zbMATH DE number 1256700 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Frozen development in graph coloring
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Many hard examples in exact phase transitions
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• 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)