Typical random 3-SAT formulae and the satisfiability threshold
Dubois, Olivier · Boufkhad, Yacine · Mandler, Jacques
Original · EN
We present a new structural (or syntatic) approach for estimating the satisfiability threshold of random 3-SAT formulae. We show its efficiency in obtaining a jump from the previous upper bounds, lowering them to 4.506. The method combines well with other techniques, and also applies to other problems, such as the 3-colourability of random graphs.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.