The Unrelated Xors problem
For the purposes of this paper, 'circuit' will refer to an object which takes a fixed number of boolean values as inputs and produces boolean values as outputs, and in the middle has a directed acyclic set of connections of one and two-valued functions (and, or, xor, etc.) and splitters, which take a single input and break it into two identical outputs. The functions and splitters are referred to as 'gates'. Two circuits are said to be equivalent if they always produce the same output regardless of the input
Conjecture - For any circuit which can be constructed using only xors and splitters, the smallest equivalent circuit by total number of gates also consists of only xors and splitters.
This conjecture is obvious. Hopefully it's also true.
It is not obvious that there are such circuits which require more than linear or near-linear numbers of gates. The following is conjectured to be an exception.
The Unrelated Xors problem - There are p2 inputs for some prime p, which will be referred to as i[x, y] where 0 <= x < p and 0 <= y < p. There are also p2 outputs, which are referred to as o[x, y] in a similar manner. Each o[x, y] is equal to the xor of all i[m, x + y*m] for 0 <= m < p.
The Unrelated Xors problem has the property that no pair of input bits are both included in two distinct output bits.
Conjecture - The smallest number of gates which can be used to construct the output of the Unrelated Xors problem using only xors is p3 - p2, which is on the order of n3/2.
This conjecture is also obvious. Hopefully it's also true.
Proving both of these conjectures would demonstrate a nontrivial complexity theoretic lower bound on runtime. Unfortunately, it would not demonstrate anything about real machines because of the implicit parallelism of memory lookups, although intuitively it seems unlikely for that to shorten runtime for this problem, and a proof of the first conjecture may work for real single processor machines as well as circuits.
by Bram Cohen May 2000