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: https://www.math.ucdavis.edu/research/...
- 8,588
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 ...
- 23k
5
votes
Accepted
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 ...
- 24.3k
5
votes
Accepted
The complexity of finding a Borsuk-Ulam point
Papadimitriou showed that a version of this problem is PPAD-complete in the paper introducing that class, "On the complexity of the parity argument and other inefficient proofs of existence".
His ...
- 7,565
4
votes
The complexity of finding a Borsuk-Ulam point
How is the oracle given and what do we know about $g$?
If the oracle is black-box and we only know that $g$ is continuous odd, then already for $n=1$ we might require infinitely many questions...
If ...
- 14k
4
votes
Accepted
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 ...
- 824
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: https://doi.org/10.1017/...
- 5,761
3
votes
Accepted
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 ...
- 1,642
3
votes
Accepted
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, ...
- 11.3k
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 ...
- 1,181
3
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}...
- 36.7k
2
votes
Accepted
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: ...
- 136
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 ...
- 28.1k
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 ...
- 119
Only top scored, non community-wiki answers of a minimum length are eligible