Classification of knots by geometrization theorem

You have all the tools to compute the geometric decomposition of knot and link exteriors in the software Regina. I'm one of the authors, although my hands haven't been over that part of the code very much. Most of the 3-manifold decomposition code was written by Ben Burton. The algorithms are primarily due to people like Rubinstein and Jaco, although Ben has done quite a lot of work to find efficient implementations of these algorithms.

Regina uses SnapPea for the hyperbolic manifolds. In a pretty strong sense it is a practical algorithm. The only part of this software for which run-time estimates do not exist is the usage of SnapPea, but in practice it is extremely fast. The primary issue with SnapPea as an algorithm is that it's not known whether SnapPea will always find a hyperbolic structure on knot and link exteriors which are hyperbolisable -- one of the key problems is finding an appropriate triangulation on which the gluing equations have a solution. I believe the precise mathematical question here is whether or not hyperbolisable 1-cusped manifolds admit an ideal triangulation. It's known such manifolds admit ideal Epstein-Penner decompositions but the facets are not always tetrahedra. One may not be able to subdivide these objects into ideal tetrahedra.

Computing the satellite decomposition tends to be slow but most of the time (as long as your diagrams aren't very complicated, say, over 50 crossings) then it performs quite well. The algorithms here tend to be exponential run time.

One of my favourite statements of geometrization for knot and link exteriors is in terms of "splicing". I wrote a survey paper on the topic.

Here is an example of using geometrization of link exteriors to answer a basic question.

Edited to reflect Igor's correction.

The precise computational complexity of the homeomorphism problem (even for knot complements in the three-sphere) is not known. It follows from work of Haken, Hemion, and Matveev that the problem for Haken manifolds is decidable (and in fact elementary recursive). Since knot complements are automatically Haken manifolds, this gives one answer to your final question (the homeomorphism problem for knots of the same type). One reference for this approach is Matveev's book "Algorithmic Topology and Classification of 3-Manifolds".

A solution to the homeomorphism problem can also be deduced from the geometrization conjecture (proven by Perelman, Hamilton). In fact, since knot complements are Haken, Thurston's earlier proof also applies. Everybody expects that the approach using geometry will be at worst simply exponential, but this is not yet proven. Igor and Ryan have already mentioned the "unreasonable effectiveness" of SnapPea/snappy and regina so I'll just leave you with several links.

See these MO questions (and this one), Matveev's book, and the program snappy for further information. The link to regina is in Ryan's answer.

I don't understand Sam Nead's statement. [He has since addressed this, but I will leave the beginning of this for context] The decidability of the homeomorphism problem for knot complements was claimed by Haken, and written down by Hemion long before geometrization was proved. One may argue that this is not "practical", but no algorithm is, while (as pointed out in the links given by Sam Nead), SnapPea essentially never fails for knots with a reasonable number of crossings. Furthermore, Alexander polynomial is polynomial time, and almost always distinguishes knots (in particular, by computing a table of Alexander polynomials for torus knots, one can usually confirm that the knot is not a torus knot. Edit in fact, the Alexander polynomial of a satellite is reducible, so if your Alexander polynomial is irreducible, you are hyperbolic.