For every even n, one can partition the edges of the complete graph on n vertices into n-1 perfect matchings such that each pair of perfect matchings forms a Hamiltonian cycle.Kotzig's conjecture is known to hold for n=2p and n=p+1 for all primes p and a few other special cases. The conjecture remains open for n=16. One would think we could solve the n=16 case by brute-force search but the search space is just too big.
This is an NP problem, one can check a partition quickly. For all those who think they have great heuristics for NP problems, go find the partition and then talk to me.
Bruck also asks how many gates does one need to solve parity on AND-OR circuits with unbounded fan-in. For n-bit inputs the answer is between 2n and 2.5n-2. The first open case comes when n=6 which requires either 12 or 13 gates. Six does not seem like a large number but still there are far too many circuits on 12 gates to check quickly.