8
$\begingroup$

Consider the projection of a knot $K$ having $n$ intersections, such as this:

Projection of an arbitrary knot

Assume we have prior information that the source knot is equally likely to be any one of the distinguishable knots having this particular projection. (One of these candidate knots is of course the trivial knot or un-knot.)

Consider an algorithm that can select and query any intersection to determine its crossing, all with a goal of determining whether the source knot $K$ is trivial or not. Note that not all intersections need be queried in order to determine this state--for instance intersection $a$ in this projection need never be queried to know that the knot is not trivial.

enter image description here

Moreover, the crossing status of some intersections can make other crossings uninformative to the task at hand.)

Suppose there is a unit cost for querying any intersection in this way. Is there an algorithm that has the lowest average total cost (total intersections queried) to determine if $K$ is trivial or not, when applied to all distinguishable knots whose projections have a given projection? What is the average expected cost, as a function of $n$, say? Can this algorithm be related to solving for a knot invariant, such as the Alexander polynomial?

(Note that this question is related to, but differs from, the problem of assigning crossings in order to unknot a given knot or from determining whether the source knot is trivial given all of the crossing information.)

Improve this question
$\endgroup$
  • $\begingroup$ A lot of what's known can be found here en.wikipedia.org/wiki/Unknotting_problem . $\endgroup$ – j.c. Sep 20 '17 at 20:49
  • 2
    $\begingroup$ Even if you query every crossing, that leaves you with a problem for which there is as yet no polynomial-time algorithm. So it seems that counting the queries is swamped by what remains. Obviously I am misunderstanding. Can you clarify? Thanks. $\endgroup$ – Joseph O'Rourke Sep 20 '17 at 22:16
  • 1
    $\begingroup$ @TimothyChow: Indeed, I do not mean that each crossing assignment is equally likely. Instead, I mean that we have one example of each fundamentally distinguishable knot that can be consistent with some assignment of the crossings given in the problem. So the unknot is always in this set. Perhaps the left and right trefoils are in the set, and so on. But there will be knots "too complicated" (i.e., having too many fundamental crossings) to be consistent with any assignment in the given projection. For instance, if the projection is a "figure 8," then the set will have just the unknot. $\endgroup$ – David G. Stork Sep 21 '17 at 18:37
  • 2
    $\begingroup$ Are you trying to win a game of knot or not? :) $\endgroup$ – Shamisen Sep 26 '17 at 19:13
  • 1
    $\begingroup$ Actually (and indirectly), yes. This question was motivated by "knot or not." $\endgroup$ – David G. Stork Nov 8 '19 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.