For this answer, we will restrict to the class of tame knots, i.e. knots that can be smoothly embedded in $S^3$.
Knot polynomials are often not complete invariants of knots and links. For example, there are several knots known to have trivial Alexander polynomial. While it is open if the unknot is detected by the Jones' polynomial, there are also knots known to have the same Jones' polynomial, for example the Kanenobu knots, named after the knots that appear in Theorem 4 the following paper:
Taizo Kanenobu, Examples on polynomial invariants of knots and links Mathematische Annalen. 1986, Volume 275, Issue 4, pp 555-572
Also, there are knots with the same HOMFLY-PT polynomial for example mutant knots, see:
W.B.R Lickorish, Linear skein theory and link polynomials, Topology and its Applications, 27 (1987), 265-274.
However, knots can be distinguished up to ambient isotopy by their complements, which is a famous (and non-trivial) theorem of Gordon and Luecke:
Cameron Gordon and John Luecke, Knots are determined by their complements. J. Amer. Math. Soc. 2 (1989), no. 2, 371–415.
It is worth mentioning that the analogous statement does not hold for links and link complements.
In terms of descriptive complexity, many upper bounds on the descriptive complexity of distinguishing knots are now framed in terms of the descriptive complexity of distinguishing a specific knot complement from another 3-manifold. Marc Lackenby's recent work along these lines shows that the unknot can be recognized in polynomial time:
Marc Lackenby, A polynomial upper bound on Reidemeister, to appear Annals of Math. Currently on the arXiv