The player spontaneously jumps back in time (Apple iMac / OS10.9.1 / Safari). Anyone else have this problem? I'd email him, if I could decipher his address! WFL On 12/30/13, Cris Moore <moore@santafe.edu> wrote:
Hass, Lagarias, and Pippenger proved that Unknot (telling whether a knot can be untied to form a simple loop) is in NP. But even proving this takes a lot of topology. The main problem is that it's not known whether there is always a series of Reidemeister moves of polynomial length (as a function of the number of initial crossings) that succeeds in untying an unknot. The best known upper bound on the number of moves is exponential, due to Hass and Lagarias.
In 2011 Kuperberg showed that Unknot is in NP \cap coNP, assuming the generalized Riemann hypothesis (!), and building on work of Koiran. Thus we don't believe that Unknot is NP-complete. However, no polynomial-time algorithm is known --- thus the mystery that it seems hard to find hard examples. (Perhaps all examples of reasonable size are too easy.)
Cris
On Dec 30, 2013, at 4:35 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
My understanding was just the opposite -- I've heard knot theorists say that they've never seen an unknot which was not 'obvious', and thus they expected the problem to be easy even though no good general methods are at hand. I have relatively little understanding of the field, personally, so I have no opinion of my own.
Charles Greathouse Analyst/Programmer Case Western Reserve University
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun