A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
type: Item
instance of: scholarly article
title: A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
zbMATH Open document ID: 1356.68113
author: Yong Gao
author: Peng Zhang
published in: Theoretical Computer Science
publication date: 2017-02-06T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q87
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 6680878
zbMATH Keywords: generalized solution concepts
zbMATH Keywords: super solutions
zbMATH Keywords: satisfiability
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: random instances
zbMATH Keywords: probabilistic method
zbMATH Keywords: threshold phenomena
MaRDI profile type: Publication
full work available at URL: j.tcs.2016.04.041
OpenAlex ID: W2416495215
cites work: The threshold for random k-SAT is 2 k (ln 2 - O(k))
cites work: A Spectral Technique for Coloring Random 3-Colorable Graphs
cites work: Q3503433
cites work: An algorithmic approach to the Lovász local lemma. I
cites work: Q4228436
cites work: Combinatorial sharpness criterion and phase transition classification for random CSPs
cites work: Frozen development in graph coloring
cites work: The \(b\)-chromatic index of graphs
cites work: Q3624064
cites work: Q3184605
cites work: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
cites work: The b-chromatic number of a graph
cites work: On Syntactic versus Computational Views of Approximability
cites work: Random constraint satisfaction: easy generation of hard (satisfiable) instances
cites work: Q4954175
cites work: Many hard examples in exact phase transitions
DOI: 10.1016/J.TCS.2016.04.041
description: scientific article; zbMATH DE number 6680878