A Remark On Random 2-SAT

It is known that almost all 2-CNF-formulas where the number of clauses is n \Delta (1 \Gamma ") ; " ? 0 a constant ; n the number of variables are satisfiable. For n \Delta (1 + ") they are shown to be unsatisfiable. We strengthen the first result and show that for each " = "(n) ( 1 ln n ) 1 2 (hence " may approach 0 ) the first of the results above still holds. 1 INTRODUCTION We consider the probability space F orm n;q of 2-CNF formulas which is obtained as follows: There are 4 \Delta i n 2 j clauses of size 2 over n variables. A random formula from F orm n;q is obtained by drawing each clause independently with probability q. Hence the expected numbers of clauses is q \Delta 4 i n 2 j . In [Go91], [ChRe91] the probability space F orm n;N is considered where F orm n;N consist of all formulas with exactly N different clauses and each formula is equally likely. As unsatisfiability is a monotone property we get from [Bo85](see. pp 33-35, theorem 2): If almost every for..