Computable link invariants I am interested in the following situation: given a braid $B$, it induces a link $L$ in a pretty straightforward way ("glue" the endpoints, like here). For a braid $B$, we know how to represent it in a normal form, which provides in particular a complete invariant of the braid (two braids have the same normal form if and only if they are equivalent). The computation of a normal form can be done efficiently. But once the link is formed... what can be done? I don't think we know any computable normal form for links... But do we know any good invariant? By "good invariant" I mean:
0) If two links are equivalent, their invariant is the same (definition of an invariant, nothing new here),
1) It can be computed in polynomial time,
2) If two links are not equivalent, they have same invariant with negligible probability (for some notion of "negligible probability"...)
 A: There are two ways to interpret your question.  
First -- since you are talking about braids, perhaps you are asking about the conjugacy problem for braids.  This is the same as taking a braid closure, with an braid axis.  In this case the ultra summit set (USS) of a braid $\sigma$ is a complete invariant for conjugacy classes.  It is an open question whether or not USS($\sigma$) is polynomial sized (and hence polynomial time computable).  There are other approaches to the conjugacy problem in braid groups, but none are know to be polynomial time. 
Second -- if you are not including the axis, then, by a result of Alexander, every link can be represented as the closure of a braid.  So your question might be: is there a polynomial time solution to the isotopy problem for links?  No such algorithm is known.  That the isotopy question is even decidable depends on Thurston's geometrization theorem for Haken manifolds; also, a great deal of work prior to Thurston is needed. 
Finally -- you ask if there is an invariant that fails with only "negligible probability".  This is a good question - I don't know the answer.  Just to make things clear.  You have the following model of random links: (a) chose a braid index, (b) choose a length, and (c) choose a random braid of that index and length in the standard generators.  Now take the closure to get a link.  This is a perfectly nice model of random links.   I suggest you consider the multi-variable Alexander polynomial. It can be computed in polynomial time, and I believe that it fails with probability tending to zero (for fixed index, and as the length tends to infinity).
EDIT:  There is a problem closely related to the conjugacy problem in the braid group; this is the determination of the Nielsen-Thurston type of a braid as either reducible or pseudo-Anosov.  This has a polynomial-time solution, due to Matthieu Calvez - see his paper Fast Nielsen-Thurston classification of braids. 
FURTHER EDIT: There have also been, very recently, claims concerning the conjugacy problem for pseudo-Anosovs (and the general conjugacy problem) in mapping class groups. Margalit, Strenner, and Yurttas have claimed a polynomial-time algorithm that, given a pseudo-Anosov, computes the veering triangulation for the associated surface bundle.  This is a complete conjugacy invariant for such mapping classes.  Here are some notes from a talk by Margalit. 
Bell and Webb are claiming a polynomial-time solution to the general conjugacy problem, based on techniques from their paper Polynomial-time algorithms for the curve graph and using some new ideas.
