4
$\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. For instance, if the three crossings in this figure are found to have the assignments shown, there is no need to query $a$ 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.)

|cite|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
  • $\begingroup$ j.c.: Yes... thanks. But as far as I can tell, all those algorithms assume the full crossing structure is known. My question assumes a cost for resolving each crossing, and that one may be able to determine whether a knot is trivial or not using a select subset of intersections. $\endgroup$ – David G. Stork Sep 20 '17 at 21:06
  • 1
    $\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
  • $\begingroup$ @JosephO'Rourke: Yes... in the worst case you must query every crossing and then have a (likely) non-polynomial problem of whether the knot is trivial. In other cases (and the average case?) you can query the right subset of intersections and can conclude that the knot is or cannot be trivial. What algorithm, when applied to every possible knot consistent with the given projection, will query the fewest crossings? Or: Suppose you know you have an example of every knot consistent with a projection $P$. What algorithm classifies all sources knots with the fewest overall crossing queries? $\endgroup$ – David G. Stork Sep 20 '17 at 22:39
  • 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

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.