Unknot recognition linear programming and the elusive polynomial time algorithm

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

• Documents
• Education
• Tuition
• Burton
• Knot theory
• Time complexity

Informations

• Published by: pefav
• Reads: 28
• Language: English
• Document size: 4 MB

Exrait

Unknotrecognition,linearprogramming dantheelusivepolynomialtime BenjaminBurton TheUniversityofQueensland June16,2011 algorithm 1/82

Outline 1 2 3 4 Decisionproblemsingeometrictopology Complexityclasses Approachesforapolynomialtimealgorithm Normalsurfacesandlinearprogramming Diagramsimplification Integerprogrammingoverhomology Averageandgenericcasecomplexity 2/28