A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming

DOI10.1016/J.TCS.2016.04.041MaRDI QIDQ507445zbMATH OpenOpenAlexFDO

Authors Yong Gao, Peng Zhang

Publication date 6 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.04.041

zbMATH Keywords

constraint satisfactiongeneralized solution conceptsprobabilistic methodrandom instancessatisfiabilitysuper solutionsthreshold phenomena

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Super solutions of random instances of satisfiability
• Super solutions of random \((3 + p)\)-SAT
• Random constraint satisfaction: A more accurate picture
• A general model and thresholds for random constraint satisfaction problems
• A probabilistic study on the satisfiability problem

Cites work

• A Spectral Technique for Coloring Random 3-Colorable Graphs
• An algorithmic approach to the Lovász local lemma. I
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Frozen development in graph coloring
• Handbook of constraint programming.
• 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?)
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Many hard examples in exact phase transitions
• On Syntactic versus Computational Views of Approximability
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• The \(b\)-chromatic index of graphs
• The b-chromatic number of a graph
• 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)

• Probabilistic estimates for the generalized maximum satisfiability problem
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Super solutions of random \((3 + p)\)-SAT
• Super solutions of random instances of satisfiability
• Expected number of locally maximal solutions for random Boolean CSPs
• On the lower bounds of \((1, 0)\)-super solutions for random \(k\)-SAT

This page was built for publication: A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507445)