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.
Our UW quantum system engineering is grappling with the following �sparsification� problem, which relates to the possibility (or not) of finding compressed representations of quantum state trajectories.
ReplyDeleteLet $\{H_i\}$ be a finite set of Hermitian matrices. Is there a unitary matrix $S$ such that each matrix $\{SH_{i}S^\dagger\}$ is sparse?
This problem obviously is in NP, the question is, is it NP-complete or NP-hard?
This �sparsification� problem turns out to be a natural question not only in physics, but also in cryptography, in the sense that key distribution schemes can be constructed in which the matrix $S$ the private key.
In the practical cases that our UW QSE Group works with, the matrices $H_i$ have dimension ~2048?2048, with about 45000 of the entries being nonzero (i.e., one percent of the entries).
Pointers to the literature would be very welcome. As far as we can tell, determining whether a given problem is NP-hard, is itself plausibly NP-hard, and reading the cryptographic literature is certainly NP-hard!
Are you sure Kotzig's conjecture is open for the case n=16? I've done a bit of searching and have seen indications in at least two places that the problem is solved when n=16.
ReplyDeleteConsider, for example, the title of this paper:
M. Meskusa, A. Rosa Perfect 1-factorizations of K_{16} with nontrivial automorphism group, Jornal of Combinatorial Mathematics and Combinatorial Computing 47 (2003) 97-111.
The previous comment is correct. The smallest open case of Kotzig's conjecture appears to be n=52. See the introduction of this paper.
ReplyDelete