Several methods of the reduction of computational complexity.
Page 1
Displaying 1 – 6 of 6
Smooth and sharp thresholds for random -XOR-CNF satisfiability
Nadia Creignou, Hervé Daudé (2003)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
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 we show the existence of a sharp threshold for the satisfiability of a random -XOR-CNF formula, whereas there are smooth thresholds for and .
Smooth and sharp thresholds for random {k}-XOR-CNF satisfiability
Nadia Creignou, Hervé Daudé (2010)
RAIRO - Theoretical Informatics and Applications
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.
Some properties of min-wise independent families and groups of permutations.
Bargachev, V. (2004)
Zapiski Nauchnykh Seminarov POMI
Sorting with a forklift.
Albert, M.H., Atkinson, M.D. (2003)
The Electronic Journal of Combinatorics [electronic only]
Stapled sequences and stapling coverings of natural numbers.
Gassko, Irene (1996)
The Electronic Journal of Combinatorics [electronic only]
Currently displaying 1 – 6 of 6
Page 1