Timeline for Computational cost of converting between 3-manifold presentations
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2011 at 14:23 | vote | accept | Gorjan Alagic | ||
| Feb 5, 2011 at 16:29 | comment | added | Bill Thurston | I've been discussing this with my son Dylan; cf. his paper with Costantino 3-Manifolds Efficiently Bound 4-manifolds, arxiv.org/pdf/math/0506577.pdf, where among other things they show a 3-manifold is obtained by (integer) surgery on a link that has crossing number quadratic in the number of simplices, and the link can be found in quadratic time. It doesn't seem obvious how to give a polynomial algorithm to give a Heegaard splitting described in terms of gluing by a word in the standard generators for the mapping class groups, but we think it's likely doable. Perhaps more later. | |
| Feb 4, 2011 at 17:21 | comment | added | Gorjan Alagic | @Bill Thurston, @Ryan Budney: Your comments are very helpful, but (due to my own lack of familiarity with the subject) I'm having trouble understanding what the conclusion is. I hope you don't mind if I rephrase my question: Is there an algorithm that, given a triangulation of a 3-manifold $M$ using $t$ tetrahedra, outputs a Dehn word $w$ in $MCG(g)$ in polynomial time, such that $|w| = poly(t)$, $g = poly(t)$, and the Heegaard splitting (g,w) is homeomorphic to $M$? | |
| Feb 4, 2011 at 8:14 | comment | added | Bruno Martelli | I don't know about tensor networks, but Turaev-Viro invariants are defined for singular triangulations as well (and more generally/dually, for simple spines). | |
| Feb 3, 2011 at 20:41 | comment | added | Bill Thurston | @Gorjan Alagic: If you really want simplicial triangulations, one procedure is to subdivide a non-simplicial trianguation mechanically, each k-simplex -> 3^k simplices, each with edges 1/3 the length of the original simplex. I suspect though that the algorithm could be reformulated using the group ring of the fundamental group so you don't need to do this; it's probably an unreasonable hit on the speed of the algorithm. | |
| Feb 3, 2011 at 19:44 | comment | added | Gorjan Alagic | @Bill Thurston: I (think I) need simplicial triangulations because I want to turn them into tensor networks for the purposes of a quantum algorithm for Turaev-Viro. There are three quantum algorithms known for computing Turaev-Viro, one for each of the 3-manifold presentation types I listed (in fact, the problem is universal in the case of H. splittings.) It would be nice to know the computational complexity (i.e., is it in $P$, $EXP$, $NP$?) of translating (using a classical computer) between these three possible input types. | |
| Feb 3, 2011 at 18:27 | comment | added | Ryan Budney | @Bill Thurston: thanks. It would be useful to have the translations encoded in an efficient way in software people could use. I'll take a closer look at your paper with Agol and Hass. | |
| Feb 3, 2011 at 18:10 | comment | added | Bill Thurston | @Ryan Budney: I didn't actually remember how complex Lickorish's description was; thanks for the comment. But curve simplification can be done efficiently, using methods like those discussed in 3-manifold knot genus is NP-complete by Agol, Hass and Thurston. I implemented this in mathematica for curves on surfaces to make sure I understood it correctly when we were writing the paper. | |
| Feb 3, 2011 at 17:53 | comment | added | Bill Thurston | @Gorjan Alagic: Why do you want simplicial triangulations? These often require a lot more simplices, and for many purposes, as long as a triangulation lifts to be simplicial in the universal covering, you can do the same things as if it were simplicial, perhaps by a little bookkeeping with the fundamental group. | |
| Feb 3, 2011 at 17:51 | comment | added | Bill Thurston | @Gorjan Alagic: Sometimes theoretically efficient algorithms are not helpful in actual implementations, because if they're more complicated they're more error-prone, especially for people implementing them mostly for themselves or a small audience. Also, even when there are linear translations from one description to another, the constants might be very important. If you have an exponential type search you want to do, then even adding a few more simplices can make the difference between feasible and unfeasible. | |
| Feb 3, 2011 at 15:28 | comment | added | Ryan Budney | Lickorish's procedure for constructing a surgery presentation from a Heegaard splitting isn't polynomial-time, at least, not as described by Lickorish. It's been a while since I looked at his argument but I believe it's an extremely inefficient argument -- likely doubly-exponential if your start-up data is a Heegaard diagram (ie the surface automorphism not yet written as a product of Dehn twists). | |
| Feb 3, 2011 at 15:18 | comment | added | Gorjan Alagic | I should add that I am actually interested in simplicial triangulations; I will edit my question to that effect. | |
| Feb 3, 2011 at 15:14 | comment | added | Gorjan Alagic | Thanks for the detailed response. I'm a little unclear on what you meant by "the challenge is in implementing them ... efficiently." Do you mean that all of these translations are in $P$, but that it might be hard to give an algorithm with a "low" power (say, linear or quadratic) running time? Or are you saying that they may not all be in $P$? | |
| Feb 3, 2011 at 7:04 | history | answered | Bill Thurston | CC BY-SA 2.5 |