Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-06T09:23:50.470Z Has data issue: false hasContentIssue false

Approximating the Satisfiability Threshold for Random k-XOR-formulas

Published online by Cambridge University Press:  17 March 2003

NADIA CREIGNOU
Affiliation:
Laboratoire d'Informatique Fondamentale de Marseille, LIF, UMR CNRS 6166, Université de la Méditerranée, Marseille, France (e-mail: creignou@lim.univ-mrs.fr)
HERVÉ DAUDÉ
Affiliation:
Centre de Mathématiques et d'Informatique, LATP, UMR CNRS 6632, Université de Provence, Marseille, France (e-mail: daude@gyptis.univ-mrs.fr)
OLIVIER DUBOIS
Affiliation:
CNRS-Université de Paris 6, LIP6, Paris, France (e-mail: Olivier.Dubois@lip6.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we study random linear systems with $k > 3$ variables per equation over the finite field GF(2), or equivalently k-XOR-CNF formulas. In a previous paper Creignou and Daudé proved that there exists a phase transition exhibiting a sharp threshold, for the consistency (satisfiability) of such systems (formulas). The control parameter for this transition is the ratio of the number of equations to the number of variables, and the scale for which the transition occurs remains somewhat elusive. In this paper we establish, for any $k > 3$, non-trivial lower and upper estimates of the value of the control ratio for which the phase transition occurs. For $k=3$ we get 0.89 and 0.93, respectively. Moreover, we give experimental results for $k=3$ suggesting that the critical ratio is about 0.92. Our estimates are clearly close to the critical ratio.

Information

Type
Research Article
Copyright
2003 Cambridge University Press