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

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.

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.)

notmean 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:37yes. This question was motivated by "knot or not." $\endgroup$ – David G. Stork Nov 8 '19 at 20:24