Personal tools
 

Computational Complexity of Knot Theory and 3-Manifold Algorithms

— filed under:

Dr. David Letscher, Oklahoma State University

What
  • Topology Seminar
When Fri, Feb 08, 2002
from 04:10 PM to 05:00 PM
Where RH 128
Add event to calendar vCal
iCal

Abstract: Among the most fundamental questions in mathematics is whether you can decide if two objects are the same. In 1961 Haken constructed an algorithm to decide if a knot is unknotted. Recent work of Hass, Lagarias and others has analyzed this algorithm to decide its computational complexity. Their results show that the unknot can be recognized in exponential time and also that the unknot recognition problem is both in NP and co-NP. A number of other problems in knot theory and 3-manifold topology are also known to be solvable. These include deciding if two knots are isotopic, 3-sphere recognition and for some classes of 3-manifolds deciding if two manifolds are homeomorphic. The computational complexity of these algorithms and others will be discussed. Also, practical implementations of these algorithms and the software package REGINA will be talked about.

« January 2018 »
January
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031
Upcoming Events
Colloquium
Fri, Jan 26, 2018
Physics in the complex domain Carl M. Bender, Washington University
Previous events…
Upcoming events…