The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem

Details The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem

2012-01-31

arxiv.org/abs/1202.0042v3

Computer Science

Discrete Mathematics

This is the long version of a paper that will be published in the SIAM Journal on Discrete Mathematics. This long version incl

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-515125