2001/06/01 by Nadia Creignou, Creignou, Nadia, Herve Daude +3
Computer Science · #Discrete Mathematics (cs.DM) #F.2.1 #FOS: Computer and information sciences #G.2m #G.3 #cs.DM
paper · pdf · doi:10.48550/arxiv.cs/0106001
15 pages, 1 figure
arxiv created 2001/06/01 · arxiv updated 2009/11/30
In this paper we study random linear systems with k variables per equation over the finite field GF(2), or equivalently k-XOR-CNF formulas. In a previous paper Creignou and Daudé proved that the phase transition for the consistency (satisfiability) of such systems (formulas) exhibits a sharp threshold. Here we prove that the phase transition occurs as the number of equations (clauses) is proportional to the number of variables. For any k≥ 3 we establish first estimates for the critical ratio. For k=3 we get 0.93 as an upper bound, 0.89 as a lower bound, whereas experiments suggest that the critical ratio is approximately 0.92.