Gibbs states and the set of solutions of random constraint satisfaction problems
Gibbs states and the set of solutions of random constraint satisfaction problems
About this item
Full title
Author / Creator
Publisher
United States: National Academy of Sciences
Journal title
Language
English
Formats
Publication information
Publisher
United States: National Academy of Sciences
Subjects
More information
Scope and Contents
Contents
An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space XN (the set of assignments). We consider two prototypical problem ensembles (random k-satisfiability and q-coloring of random regular graphs) and study the uniform measure with support on S. As the number of constraints...
Alternative Titles
Full title
Gibbs states and the set of solutions of random constraint satisfaction problems
Authors, Artists and Contributors
Identifiers
Primary Identifiers
Record Identifier
TN_cdi_pubmedcentral_primary_oai_pubmedcentral_nih_gov_1965511
Permalink
https://devfeature-collection.sl.nsw.gov.au/record/TN_cdi_pubmedcentral_primary_oai_pubmedcentral_nih_gov_1965511
Other Identifiers
ISSN
0027-8424
E-ISSN
1091-6490
DOI
10.1073/pnas.0703685104
