HTTPS SSH

Orbits

Copyright © 2017, Marc Culler


Description

In a remarkable paper by Ian Agol, Joel Hass and Bill Thurston it was shown that the problem of deciding whether a knot has a genus g spanning surface is NP complete. Along the way, the authors described an algorithm for solving the following problem:

  • Given an equivalence relation on the set J = {1, ..., N} which
    is generated by k order preserving or order reversing pairings
    between subintervals of J, compute the number of equivalence
    classes.

They showed that the running time of the algorithm is amazingly fast -- bounded by a polynomial in k log N.

Orbits is a python module which implements their algorithm.


Installation

This is a simple python module consisting of a single file. To install it run

python setup.py install

or, on linux,

sudo python setup.py install

A simple example computation is provided in the file example.py.