Phase transitions of random constraint satisfaction problems

DOI10.4310/CDM.2018.V2018.N1.A5MaRDI QIDQ5133620zbMATH OpenFDO

Authors Allan Sly

Publication date 10 November 2020

Published in Current Developments in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4310/CDM.2018.V2018.N1.A5

zbMATH Keywords

colouringsphase transitionsrandom graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Recommendations

• On the phase transitions of random \(k\)-constraint satisfaction problems
• scientific article; zbMATH DE number 7301529
• The replica symmetric phase of random constraint satisfaction problems
• Phase transitions in discrete structures
• Models for Random Constraint Satisfaction Problems

Cited in

(14)

• Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
• Phase transitions in discrete structures
• On the freezing of variables in random constraint satisfaction problems
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Random instances of problems in NP -- algorithms and statistical physics
• scientific article; zbMATH DE number 2046061 (Why is no real title available?)
• Phase Transition for Maximum Not-All-Equal Satisfiability
• The condensation phase transition in the regular $k$-SAT model
• The replica symmetric phase of random constraint satisfaction problems
• Optimization of the dynamic transition in the continuous coloring problem
• Gibbs states and the set of solutions of random constraint satisfaction problems
• On the phase transitions of random \(k\)-constraint satisfaction problems
• scientific article; zbMATH DE number 6469137 (Why is no real title available?)
• A continuous constraint satisfaction problem for the rigidity transition in confluent tissues

This page was built for publication: Phase transitions of random constraint satisfaction problems

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