Skip to main content
9 votes

Complexity of Unknotting problems

Such a quasi-polynomial algorithm has just been claimed by Marc Lackenby from Oxford University. He will present in next Tuesday (02 Feb 2021) in a Zoom talk:
Denis's user avatar
  • 8,903
6 votes

Reference request: Shortest homotopic curve via vertex releases

This is morally equivalent to a slower variant of the Hershberger-Snoeyink funnel algorithm. I'm not aware of any exposition of your simple algorithm in the literature. This is actually a little ...
Jeffε's user avatar
  • 23.2k
5 votes

Is minimum knot crossing number elementary recursive?

The number of graphs on $n$ vertices is $$2^{\frac{n(n-1)}{2}}.$$ The number of embeddings of a degree 4 planar graph with $n$ vertices is at most $6^n$. (If you know the clockwise order of the ...
Peter Shor 's user avatar
4 votes

Is the 3-sphere recognition problem NP-complete?

This paper shows (though I have not verified it) that 3-sphere recognition* is in coNP assuming GRH: Raphael Zentner. Integer homology 3-spheres admit irreducible representations in $SL(2,\mathbb{C})$...
Joshua Grochow's user avatar
4 votes

What are the application of Scott-Topology in theoretical computer science?

Scott-continuity emerged when Dana Scott build the first model of untyped λ-calculus, while trying to prove that no such model can exist (since any such model $D$ needs to be, simplifying a bit, ...
Martin Berger's user avatar
4 votes

Status of certain problems in knot theory

To complete the first answer, the equivalence problem is decidable (this dates back to haken, a good reference is Lackenby's survey Elementary Knot Theory ). It is neither known to be in NP nor known ...
Arnaud's user avatar
  • 834
4 votes

Status of certain problems in knot theory

Regarding the HOMPFLY-PT polynomial, evaluating the coefficients of the Jones polynomial is #P-hard, and this of course transfers to the more general HOMPFLY-PT polynomial:
Hermann Gruber's user avatar
3 votes

Complexity of Unknotting problems

The outline from Marc Lackenby's talk about a quasipolynomial algorithm for Unknottedness. Unknot recognition in quasipolynomial time outline.. Under the talks section there are slides about the ...
user3483902's user avatar
  • 1,261
3 votes

How to design an algorithm which turns an undirected graph into directed with all nodes of indegree higher than 0?

Edit: modified to emphasize how this approach can be generalized to any arbitrary degree sequence of lower bound in-degrees. (Apologies if the below is extra verbose -- you said that you're new to ...
Yonatan N's user avatar
  • 1,642
2 votes

Data structures for embedded simplicial complexes

First you can read the CGAL documentation that can help you to understand combinatorial and generalized maps, since it provide several examples. You can also read the book "Combinatorial Maps: ...
gdamiand's user avatar
  • 136
1 vote

algebraic topology in distributed computing

Maurice Herlihy, Dmitry Kozlov and Sergio Rajsbaum, "Distributed Computing Through Combinatorial Topology", 2014
Kaveh's user avatar
  • 21.7k
1 vote

Topology/Space of Recursive Algebraic Datatypes

It is possible to construct recursive datatypes (algebraic datatypes are a special case) in a suitable category of complete metric spaces, see for instance P. America and J. Rutten's Solving Reflexive ...
Andrej Bauer's user avatar
  • 29.2k
1 vote

Why is "topological sorting" topological?

Topology is the study of how "shapes" change when you apply continuous transformations to them. The central object of study is a topological space, which can be thought of as a way of saying ...
user513093's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible