The satisfiability threshold for a seemingly intractable random constraint satisfaction problem

DOI10.1137/090777268MaRDI QIDQ2910950zbMATH OpenOpenAlexFDO

Authors Harold Connamacher, Michael Molloy

Publication date 12 September 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.0042

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Error analysis and interval analysis (65G99) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Abstract: We determine the exact threshold of satisfiability for random instances of a particular NP-complete constraint satisfaction problem (CSP). This is the first random CSP model for which we have determined a precise linear satisfiability threshold, and for which random instances with density near that threshold appear to be computationally difficult. More formally, it is the first random CSP model for which the satisfiability threshold is known and which shares the following characteristics with random k-SAT for k >= 3. The problem is NP-complete, the satisfiability threshold occurs when there is a linear number of clauses, and a uniformly random instance with a linear number of clauses asymptotically almost surely has exponential resolution complexity.

Recommendations

• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• A sharp threshold for a random constraint satisfaction problem
• The Resolution Complexity of Random Constraint Satisfaction Problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Proof of the satisfiability conjecture for large k

Cited in

(23)

• On unique satisfiability and the threshold behavior of randomized reductions
• Threshold behaviors of a random constraint satisfaction problem with exact phase transitions
• The satisfiability threshold for random linear equations
• Many hard examples in exact phase transitions
• On the freezing of variables in random constraint satisfaction problems
• The structure of the set of satisfying assignments for a random \(k\)-CNF
• Resolution complexity of random constraint satisfaction problems: Another half of the story
• Threshold properties of random Boolean constraint satisfaction problems
• A dichotomy theorem for the resolution complexity of random constraint satisfaction problems
• Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
• Lower and Upper Bounds for Random Mimimum Satisfiability Problem
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Bounding the unsatisfiability threshold of random 3-SAT
• scientific article; zbMATH DE number 2083805 (Why is no real title available?)
• On the uniformity of the approximation for r-associated Stirling numbers of the second kind
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Satisfiability threshold for power law random 2-SAT in configuration model
• Random constraint satisfaction: Flaws and structure
• Uniform convergence of an asymptotic approximation to associated Stirling numbers
• Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
• Spines of random constraint satisfaction problems: definition and connection with computational complexity

This page was built for publication: The satisfiability threshold for a seemingly intractable random constraint satisfaction problem

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