Approximating the satisfiability threshold for random k-XOR-formulas
| dc.creator | Creignou, Nadia | |
| dc.creator | Daude, Herve | |
| dc.creator | Dubois, Olivier | |
| dc.date | 2001-06-01 | |
| dc.date.accessioned | 2026-07-07T03:17:10Z | |
| dc.date.available | 2026-07-07T03:17:10Z | |
| dc.description | 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\ge 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. | |
| dc.description | 15 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/cs/0106001 | |
| dc.identifier | http://arxiv.org/abs/cs/0106001 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30624 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.1; G.2m; G.3 | |
| dc.title | Approximating the satisfiability threshold for random k-XOR-formulas | |
| dc.type | text |