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

- 13k

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

- 83

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

#### Related Tags

algorithms × 1456graph-theory × 318

co.combinatorics × 301

computational-complexity × 218

nt.number-theory × 193

linear-algebra × 116

computer-science × 82

reference-request × 76

gr.group-theory × 72

mg.metric-geometry × 71

pr.probability × 66

computational-geometry × 61

computational-number-theory × 54

combinatorial-optimization × 54

ag.algebraic-geometry × 52

polynomials × 52

approximation-algorithms × 52

na.numerical-analysis × 48

matrices × 44

discrete-geometry × 43

oc.optimization-and-control × 41

prime-numbers × 37

ac.commutative-algebra × 36

linear-programming × 35

graph-colorings × 28