tag:blogger.com,1999:blog-3722233.post114312027127305964..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Large Search Problems for Small InputsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1144708022395103242006-04-10T17:27:00.000-05:002006-04-10T17:27:00.000-05:00The previous comment is correct. The smallest ope...The previous comment is correct. The smallest open case of Kotzig's conjecture appears to be n=52. See the introduction of <A HREF="http://www.combinatorics.org/Volume_12/PDF/v12i1r1.pdf" REL="nofollow">this paper</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143570314169570652006-03-28T12:25:00.000-06:002006-03-28T12:25:00.000-06:00Are you sure Kotzig's conjecture is open for the c...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. <BR/><BR/>Consider, for example, the title of this paper: <BR/><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1143221298334735032006-03-24T11:28:00.000-06:002006-03-24T11:28:00.000-06:00Our UW quantum system engineering is grappling wit...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.<BR/><BR/>Let $\{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?<BR/><BR/>This problem obviously is in NP, the question is, is it NP-complete or NP-hard?<BR/><BR/>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.<BR/><BR/>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).<BR/><BR/>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!Anonymousnoreply@blogger.com