28 Pages
English
Gain access to the library to view online
Learn more

Unknot recognition linear programming and the elusive polynomial time algorithm

-

Gain access to the library to view online
Learn more
28 Pages
English

Description

Unknot recognition, linear programming and the elusive polynomial time algorithm Benjamin Burton The University of Queensland June 16, 2011 1 / 28

  • unknot figure

  • knot theory

  • diagram simplification

  • rubber-sheet geometry

  • dimensional surface

  • polynomial time algorithm


Subjects

Informations

Published by
Reads 28
Language English
Document size 4 MB

Exrait

Unknotrecognition,linearprogrammingdantheelusivepolynomialtimeBenjaminBurtonTheUniversityofQueenslandJune16,2011algorithm1/82
Outline1234DecisionproblemsingeometrictopologyComplexityclassesApproachesforapolynomialtimealgorithmNormalsurfacesandlinearprogrammingDiagramsimplificationIntegerprogrammingoverhomologyAverageandgenericcasecomplexity2/28