Models for Random Constraint Satisfaction Problems

DOI10.1137/S0097539700368667MaRDI QIDQ4706240zbMATH OpenFDO

Authors

Publication date 19 June 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539700368667

zbMATH Keywords

constraint satisfaction problemsrandom modelssharp thresholdthreshold

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Recommendations

• scientific article; zbMATH DE number 5547880
• A general model and thresholds for random constraint satisfaction problems
• scientific article; zbMATH DE number 7301529
• Random constraint satisfaction: Flaws and structure
• Principles and Practice of Constraint Programming – CP 2004
• scientific article; zbMATH DE number 1002207
• scientific article; zbMATH DE number 2010170
• Randomized approximation of the constraint satisfaction problem
• The Resolution Complexity of Random Constraint Satisfaction Problems
• On the solution-space geometry of random constraint satisfaction problems

Cited in

(31)

• The SAT-UNSAT transition for random constraint satisfaction problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• When does the giant component bring unsatisfiability?
• Backtracking and random constraint satisfaction
• A probabilistic analysis of randomly generated binary constraint satisfaction problems.
• Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities
• Many hard examples in exact phase transitions
• On the freezing of variables in random constraint satisfaction problems
• A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
• An algorithm for random signed 3-SAT with intervals
• Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration
• Satisfiability thresholds beyond k-XORSAT
• On Random Ordering Constraints
• Conditional random fields, planted constraint satisfaction, and entropy concentration
• A general model and thresholds for random constraint satisfaction problems
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• scientific article; zbMATH DE number 5547880 (Why is no real title available?)
• Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
• Phase transitions of random constraint satisfaction problems
• scientific article; zbMATH DE number 7301529 (Why is no real title available?)
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Streamlining variational inference for constraint satisfaction problems
• Principles and Practice of Constraint Programming – CP 2004
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: Flaws and structure
• Bounding the scaling window of random constraint satisfaction problems
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• The scaling window of the model \(d\)-\(k\)-CSP
• Random subcubes as a toy model for constraint satisfaction problems

This page was built for publication: Models for Random Constraint Satisfaction Problems

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