The aim of this paper is to study the threshold behavior for the satisfiability property of a random k-XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with k variables per equation. For k ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random k-XOR-CNF formula, whereas there are smooth thresholds for k=1 and k=2.
No takes yet. Share an insight, caveat, or question.
Creignou et al. (2003) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: