A new upper bound for 3-SAT

Details A new upper bound for 3-SAT A new upper bound for 3-SAT

2008-07-23

arxiv.org/abs/0807.3600v1

Computer Science

Discrete Mathematics

20 pages

Scientific paper

We show that a randomly chosen 3-CNF formula over n variables with clauses-to-variables ratio at least 4.4898 is, as n grows large, asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was 4.506. The first such bound, independently discovered by many groups of researchers since 1983, was 5.19. Several decreasing values between 5.19 and 4.506 were published in the years between. The probabilistic techniques we use for the proof are, we believe, of independent interest.

Affiliated with

Also associated with

No associations

Rating

A new upper bound for 3-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 A new upper bound for 3-SAT, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new upper bound for 3-SAT will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-544