Phase Transition in Unrestricted Random SAT

Details Phase Transition in Unrestricted Random SAT Phase Transition in Unrestricted Random SAT

2012-04-07

arxiv.org/abs/1204.1656v1

Computer Science

Computational Complexity

14 pages

Scientific paper

For random CNF formulae with m clauses, n variables and an unrestricted number of literals per clause the transition from high to low satisfiability can be determined exactly for large n. The critical density m/n turns out to be strongly n-dependent, ccr = ln(2)/(1-p)^^n, where pn is the mean number of positive literals per clause.This is in contrast to restricted random SAT problems (random K-SAT), where the critical ratio m/n is a constant. All transition lines are calculated by the second moment method applied to the number of solutions N of a formula. In contrast to random K-SAT, the method does not fail for the unrestricted model, because long range interactions between solutions are not cut off by disorder.

Affiliated with

Also associated with

No associations

Rating

Phase Transition in Unrestricted Random SAT 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 Phase Transition in Unrestricted Random SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase Transition in Unrestricted Random SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-37331