Coarse and sharp transitions for random generalized satisfiability problems

MaRDI QIDQ3154710zbMATH OpenFDO

Authors Nadia Creignou, Hervé Daudé

Publication date 14 January 2005

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Threshold properties of random Boolean constraint satisfaction problems
• Generalized satisfiability problems: Minimal elements and phase transitions.
• A sharp threshold for a random constraint satisfaction problem

Cited in

(8)

• The SAT-UNSAT transition for random constraint satisfaction problems
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Threshold properties of random Boolean constraint satisfaction problems
• A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas
• Random 2-XORSAT at the Satisfiability Threshold
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Random 2 XORSAT phase transition
• 2-Xor revisited: satisfiability and probabilities of functions

This page was built for publication: Coarse and sharp transitions for random generalized satisfiability problems

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