SMOOTH AND SHARP THRESHOLDS FOR RANDOM κ-XOR-CNF SATISFIABILITY

摘要

The aim of this paper is to study the threshold behavior for the satisfiability property of a random κ-XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with κ variables per equation. For κ ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random κ-XOR-CNF formula, whereas there are smooth thresholds for κ = 1 and κ = 2.