11 votes
Accepted

Is there an algorithm for the genus of a knot?

Jaco and Oertel's paper An algorithm to decide if a three-manifold is a Haken manifold [1984], plus a bit of work, gives a doubly exponential time algorithm to compute the Seifert genus. (In practice ...
  • 20.4k
11 votes

Is there an algorithm for the genus of a knot?

There is an algorithm using normal surface theory, originally developed by Haken and Schubert to compute the genus of any knot. These articles are in German, but for a reference in English, one could ...
  • 1,587
6 votes

Is there an algorithm for the genus of a knot?

I think it's usually easier in practice, but knot Floer homology determines the genus (and is algorithmically computable from a diagram). See Ozsváth and Szabó's paper "Holomorphic disks and ...
3 votes

Is there an algorithm for the genus of a knot?

In addition to the references given in the other answers, Lackenby has shown that recognition of the Seifert genus is in NP. This is based on a taut sutured manifold hierarchy for the knot complement ...
  • 62.2k
1 vote

Popular algorithms (stopping rules) with output - a prefix of a permutation

Generalized Secretary Problems: One flavour is as follows. Consider the general $(J, K)-$secretary problem, where $n$ totally ordered items arrive in a random order. An algorithm observes the relative ...
  • 8,861
1 vote

Deciding positivity of real cyclotomic numbers efficiently

This is a particular case of a more general problem of deciding if a real algebraic number is positive. Or even of a more general problem, deciding if a semialgebraic set is non-empty. Let $\Psi_n(t)$ ...
1 vote

Representing mathematical statements as SAT instances

If you can write down your mathematical statement in propositional logic, you might want to check out our tool at https://github.com/peitl/short-proof, which does what you're asking for propositional ...

Only top scored, non community-wiki answers of a minimum length are eligible