21

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 nontermination are not symmetric. It is possible to observe whether a black-box program terminates (simply wait long enough), but it's not possible to observe whether it ...


16

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 and Defintion 11.2.10 of the HoTT book.) The following theorem is valid in any topos (a model of higher-order intuitionistic logic): Theorem: There is a ...


15

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 nodes and the nodes are assumed to be numbered by a non-topological system. Given a list of these lines in numeric order, a simple technique can be used to create ...


12

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 dimensional topological approaches to topics in the theory of computation, all fairly new: Various approaches to fault-tolerant anyonic quantum computation based on ...


9

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 introductory posts on the blog "Low Dimensional Topology" : http://ldtopology.wordpress.com/2014/05/04/low-dimensional-topology-of-information/


9

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 graph. Betti-1 will be one interval for each essential closed loop; corresponding to a running updated basis for the Cycle Space. Since it is a graph, these ...


8

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 and Freedman-Kitaev-Wang proved that a quantum computer can "additively" approximate the Jones polynomial at a root of unity in polynomial time. Furthermore, by ...


6

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 surprising, given how many times the basic funnel algorithm has been rediscovered [Tompa, STOC 1980; Chazelle, FOCS 1982; Lee and Preparata, Networks 1984; ...


6

A fixed point of a best response function is a Nash equilibrium -- the fact that you do not have the payoff matrix cannot make the problem easier (since if you know the payoff matrix, you also know the best response function, but not vice versa). Unfortunately, there are not in general good algorithms for computing approximate Nash equilibria in multi-player ...


5

For each $n \geq 0$, the word $aaba^nb^{n+1}$ is in $D$, therefore $aaba^\omega$ is in $Adh(D)$.


5

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 formulation of the problem is: Borsuk-Ulam. Given an integer n and a Turing machine computing for each point $P=(x_1,\dots,x_d)$ with $-n\leq x_i\leq n$ and $\...


4

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-Set Agreement Is Impossible: The Topology of Public Knowledge. By Michael Saks and Fotios Zaharoglou, SIAM J. on Computing, Vol. 29 (2000), 1449-1483. Quotes ...


4

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 characterized using topology. Defining Liveness Alpern and Schneider Safety and Liveness in Branching time Manolios et. al.


4

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 the oracle is given by some Turing-machine, then you get that your problem is FIXP-complete, PPAD-complete, where the size of the input is length of $\epsilon$...


3

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 that the complex at step k is a subset of the complex at step k+1 i.e. the vertices and edges are inserted into it in some order. Assuming that the vertices ...


3

Ryan Budney has started similar discussions at MathOverFlow: https://mathoverflow.net/questions/35946/how-expensive-is-knowledge-knots-links-3-and-4-manifold-algorithms https://mathoverflow.net/questions/144158/what-is-the-state-of-the-art-for-algorithmic-knot-simplification/145927 and at Wikipedia: http://en.wikipedia.org/wiki/Talk:...


3

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})$. arXiv:1605.08530 [math.GT], 2016 (Of possible interest: a follow-up paper arXiv:1610.04092 [math.GT] uses this to develop an algorithm using Grobner bases....


3

You may want to look at nowhere dense graphs. http://www.sciencedirect.com/science/article/pii/S0195669811000151 One of the reasons why minor-closedness is natural is the following. We typically want to work with families of graphs rather than specific graphs. And we want to solve problems with arbitrary weights/capacities on edges/nodes. Suppose we want to ...


3

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 graph algorithms, and I want to make sure you can follow the reasoning.) Your problem is a special case of the Santa Clause problem, and the (significantly) more ...


2

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: Efficient Data Structures for Computer Graphics and Image Processing". Now some answers: 1) I don't think. In a combinatorial map, in 2D, a triangle is described by ...


1

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 Domain Equations in a Category of Complete Metric Spaces, Journal of Computer and System Sciences 39, 343-375 (1989). As for making vector spaces out of ...


1

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 Rips complex you can actually find higher dimensional homology as well. For instance the persistence betti numbers for N points equally space on a circle look ...


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