# Tag Info

Accepted

### Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

One major application of topology in semantics is the topological approach to computability. The basic idea of the topology of computability comes from the observation that termination and ...
• 31.6k
Accepted

### Why is "topological sorting" topological?

The earliest reference I could find for topological sort is from [Lasser61]: A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal ...
• 3,381
Accepted

### To what extent can the mathematics of Reals be applied to Computable Reals?

The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 ...
• 26.6k

### Applications of topology to computer science

Nobody has yet mentioned directed algebraic topology, which was in fact developed to provide a suitable algebraic topological toolbox for the study of concurrency. There are also several low ...

### 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/...
• 7,653
Accepted

### Barcode of a graph

Betti-0 will be one interval for each vertex, with one of the involved intervals vanishing any time an edge connects two components. This will be very similar to a trace of a Union-Find running on the ...

### Would a purely topological computational model be useful in decision problems in topology?

Avishy Carmi and Daniel Moskovich have been developing tangle machines very recently, which is a topological model to describe information. There are two papers on the arXiv, as well as three ...
• 824
Accepted

### Would a purely topological computational model be useful in decision problems in topology?

I'm not sure whether this qualifies as a purely topological computational model, but there is a topological approach to anyonic quantum computation within the framework of which Aharonov-Jones-Landau ...

### 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 ...
• 22.8k
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,052
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

### 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,424

### Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

The 2004 Gödel Prize was shared between the papers: The Topological Structure of Asynchronous Computation. By Maurice Herlihy and Nir Shavit, Journal of the ACM, Vol. 46 (1999), 858-923 Wait-Free k-...
• 2,319

### Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?

Behavior of a reactive system is often modeled using infinite structures ( infinite traced and infinite computation trees) and their Temporal properties (safety and liveness properties) have also been ...
• 41

### 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 ...
• 13.5k

### Barcode of a graph

The graph is already a simplicial complex comprising of 0 and 1 simplices (nodes and edges). The barcode representation is meaningful only when the simplicial complex is constructed step-by-step such ...
• 31

• 10.3k

### 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,081
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 ...
• 26.6k
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
1 vote

### Barcode of a graph

What is said above is correct but I'll add an interesting wrinkle that should be better known. If you use the graph distance as your persistence parameter and then calculate the persistence of the ...
• 111

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