Showing cs.DMShow all
2 papers · 1 filter
cs.DM2009
The threshold for random (1,2)-QSAT
Nadia Creignou, Herve Daude, Uwe Egly +1
The QSAT problem is the quantified version of the SAT problem. We show the existence of a threshold effect for the phase transition associated with the satisfiability of random qua…
cs.DM2001
Approximating the satisfiability threshold for random k-XOR-formulas
Nadia Creignou, Herve Daude, Olivier Dubois
In this paper we study random linear systems with variables per equation over the finite field GF(2), or equivalently -XOR-CNF formulas. In a previous paper Creignou and Dau…