Unknot recognition linear programming and the elusive polynomial time algorithm

Benjamin Burton

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

Sujets

• Burton
• Knot theory
• Time complexity

Informations

• Publié par: pefav
• Nombre de lectures: 28
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

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

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