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

DOI10.1016/J.TCS.2016.04.041zbMATH Open1356.68113OpenAlexW2416495215MaRDI QIDQ507445FDOQ507445

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

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

zbMATH Keywords

constraint satisfactionsatisfiabilityprobabilistic methodrandom instancesgeneralized solution conceptssuper solutionsthreshold phenomena

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)

Cites Work

• Handbook of constraint programming.
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Frozen development in graph coloring
• The b-chromatic number of a graph
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• An algorithmic approach to the Lovász local lemma. I
• 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
• On Syntactic versus Computational Views of Approximability
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• The \(b\)-chromatic index of graphs
• The threshold for random k-SAT is 2 ^k (ln 2 - O(k))

Cited In (6)

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

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)