Several methods of the reduction of computational complexity.
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 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
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.
Sorting with a forklift.
Stapled sequences and stapling coverings of natural numbers.