Skip to main content
The 2024 Developer Survey results are live! See the results

Questions tagged [topology]

Topology the study of objects that can be continuously deformed into other objects without tearing or making holes in the object. It can also mean a family of sets that have the property of a topological space. The properties are convergence, connectedness, and continuity.

Filter by
Sorted by
Tagged with
9 votes
1 answer
226 views

algebraic topology in distributed computing

I have just discovered the paper of M. Herlihy and N. Shavit on the use of algebraic topology methods in TCS and distributed computing in particular. Now I am wondering if there is any further work ...
timtombobjohn's user avatar
3 votes
1 answer
135 views

Is minimum knot crossing number elementary recursive?

One result in knot theory is that link crossing number is NP-hard. Another result is that the equivalence problem for knots and links is elementary recursive. So, given that the equivalence problem is ...
Niklas Rosencrantz's user avatar
8 votes
1 answer
374 views

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

During a work I came across the Scott-Topology and I see that Scott-continuous functions show up in the study of models for lambda calculi. What I cannot understand is how this enrich the lambda-...
micrus's user avatar
  • 91
2 votes
2 answers
389 views

Status of certain problems in knot theory

I found it somewhat difficult to understand the status of certain problems from knot theory. Is it correct to say that it's been neither proved nor disproved that any of the following problems are NP-...
Niklas Rosencrantz's user avatar
3 votes
0 answers
89 views

Using Baire Category to analyze the efficiency of the Simplex Method

I read from the wiki page of the Simplex Algorithm that we can "use Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the ...
Ruiyuan Huang's user avatar
5 votes
0 answers
195 views

Abstract stone duality and cohesive homotopy type theory

I have been reading the real-cohesive homotopy type theory paper and one of the remarks has sparked an interest. In this paper a string of monadic and comonadic modalities is introduced together with ...
Ilk's user avatar
  • 920
6 votes
2 answers
489 views

Complexity of Unknotting problems

The complexity of the Unknotting problem is known to be in $\mathrm{NP} \cap\mathrm{co\text-NP}$, see references: The Computational Complexity of Knot Problems. Knottedness is in NP, modulo GRH. . ...
user3483902's user avatar
  • 1,261
2 votes
1 answer
138 views

Data structures for embedded simplicial complexes

I am looking for a data structure to encode an $n$-dimensional simplicial complex with an embedding in $\mathbb{R}^{n+1}$. I am aware of combinatorial maps, which generalize rotation systems of planar ...
Will's user avatar
  • 215
7 votes
1 answer
184 views

Reference request: Shortest homotopic curve via vertex releases

Let $C$ be a piecewise-linear path (or closed curve) in the plane, in the presence of polygonal obstacles. We would like to find the shortest path (or curve) homotopic to $C$. (A path $D$ is homotopic ...
Gabriel Nivasch's user avatar
11 votes
0 answers
217 views

Do Banach spaces and linear contraction maps form a model of ILL with an exponential?

Recently, I read on the nLab that the category of Banach spaces and linear contractions is small complete, small cocomplete, and monoidal closed. This means that Banach spaces and short linear maps ...
Neel Krishnaswami's user avatar
5 votes
1 answer
138 views

Topology/Space of Recursive Algebraic Datatypes

I have a recursive algebraic datatype. I (somewhat arbitrarily) defined one function to compute distance between instances, and am trying to define a function to approximate a "vector" between ...
lightning's user avatar
  • 433
0 votes
1 answer
2k views

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

Given an undirected graph $G=(V,E)$ devise an algorithm that will check whether its edges can be directed in such a way that the vertices of the resulting directed graph will all have indegree higher ...
Yos's user avatar
  • 111
5 votes
0 answers
127 views

Structures obtained by gluing simplices

I'm looking for the correct name of geometric structures obtained as follows. 2-structures: A collection $X$ of triangles is a $2$-structure. If $X$ is a $2$-structure and $Y$ is obtained from $X$ ...
Mateus de Oliveira Oliveira's user avatar
9 votes
0 answers
328 views

Applications of "Seemingly Impossible Functional Programs"

What are some practical applications (existing or potential) for Martin Escardo's "Seemingly Impossible Functional Programs"? For starters, here are a few from: Alex Simpson’s Lazy functional ...
NietzscheanAI's user avatar
0 votes
0 answers
153 views

Approximating liveness properties with safety properties

Given a finite alphabet set $\Sigma$, the set $\Sigma^{\omega}$ of infinite words over $\Sigma$ can be topologized with a metric $d: \Sigma^{\omega} \rightarrow \mathbb{R}$ such as: $\forall w_1, w_2 ...
Ahmed Nassar's user avatar
10 votes
2 answers
410 views

The complexity of finding a Borsuk-Ulam point

The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$. Simmons and Su (2002) describe a method ...
Erel Segal-Halevi's user avatar
16 votes
3 answers
703 views

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

I am a mathematician interested in set theory, ordinal theory, infinite combinatorics and general topology. Are there any applications for these subjects in computer science? I have looked a bit, and ...
user135172's user avatar
37 votes
4 answers
3k views

Why is "topological sorting" topological?

Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why ...
PartialOrder's user avatar
1 vote
0 answers
120 views

Example of non-disk bounding planarly nested sequences of cycles

I am trying to find an example for the Theorem 5.1 of the paper "Combinatorial Local Planarity and the Width of Graph Embeddings" that can be found at http://www.fmf.uni-lj.si/~mohar/Reprints/1992/...
Hung Le's user avatar
  • 305
16 votes
1 answer
1k views

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

Is there a general theorem that would state, with proper sanitization, that most known results regarding the use of real numbers can actually be used when considering only computable reals? Or is ...
babou's user avatar
  • 1,542
6 votes
2 answers
577 views

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

If one were to develop a purely topological computational model based upon the equivalence of information in knots and the model would perform transformations of that information. This would be the ...
Joshua Herman's user avatar
8 votes
3 answers
600 views

Barcode of a graph

Using persistent homology, we can analyze the (topological) shape of a cloud of points using the following three-step method: convert the point set into a simplicial complex (and there are a few ...
Suresh Venkat's user avatar
4 votes
1 answer
154 views

Generalizations of planar graphs that include hypercubes with large side length in $R^d$

A lot of people have asked about generalizations of planar graphs on other forums. Some topics include: https://mathoverflow.net/questions/7650/generalizations-of-planar-graphs https://math....
Aaron Schild's user avatar
3 votes
1 answer
467 views

How do you compute the fixed point of a best-response function efficiently?

I have a polynomial time best-response function that has the same properties as a game-theory game (convexity, compactness, set-valued). I don't know that much topology, but my understanding is that ...
user avatar
1 vote
1 answer
451 views

Adherence of languages and the Dyck language

Let $L \subseteq X^*$ and $X = \{a,b\}$ be a language of finite words, denote by $A(u)$ the prefixes of some word (finite or infinite), then the adherence $\mbox{Adh}(L)$ is defined to be the set of ...
StefanH's user avatar
  • 2,057
3 votes
0 answers
115 views

Transfering properties from subsets of $X^*$ to subsets of $X^{\omega}$ by using the topology induces by Cantor space

A language $L \subseteq X^*$ is non-counting of order $n > 0$ iff for all $u,v, w \in X^*$ $$ uv^nw \in L \Leftrightarrow uv^{n+1} w \in L. $$ A $\omega$-language (set of infinite sequences) $L \...
StefanH's user avatar
  • 2,057
19 votes
1 answer
312 views

Is there a geometrical picture for adiabatic quantum computation?

In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily ...
hadsed's user avatar
  • 431
2 votes
0 answers
138 views

test if a polygon-surface is closed (+ additional nice-to-have requirements)

I have a 3D object bounded by Polygons. Is there a standard algorithm that tests if the volume is closed e.g. no polygon is missing? Example: I have a cube bounded by six squares. The algorithm ...
Simon Fromme's user avatar
7 votes
2 answers
221 views

Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions

Consider a planar subdivision, with F faces, V vertices, E edges, and I face-vertex incidences. For simplicity, assume a "non-degenerate" situation in which each vertex occurs on the boundary cycle of ...
Herman Haverkort's user avatar
0 votes
1 answer
313 views

Is there a characteristic function of a tree?

Consider a set of trees $T=\{T_{\alpha}\}$, and for any $T_{\alpha}\in T$, $T_{\alpha}$ has $n$ nodes. Can we find a ‘characteristic’ function $f:T\longmapsto{\mathbb{R}}$ describing trees' ...
zenos's user avatar
  • 69
19 votes
1 answer
838 views

A topological space related to SAT: is it compact?

The Satisfiability problem is, of course, a fundamental problem in theoretical CS. I was playing with one version of the problem with infinitely many variables. $\newcommand{\sat}{\mathrm{sat}} \...
Srivatsan Narayanan's user avatar
5 votes
1 answer
541 views

Place n points in a box as far away from each other as possible

Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized. In other words, I'm ...
Alan Turing's user avatar
1 vote
1 answer
213 views

Computational Library to compute Quantum Cluster States

I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? ...
Joshua Herman's user avatar
27 votes
2 answers
1k views

Complexity of Topological Properties.

I am a computer scientist taking a course on Topology (a sprinkling of point-set topology heavily flavored with continuum theory). I have become interested in decision problems testing a description ...
Ross Snider's user avatar
  • 2,045
12 votes
1 answer
472 views

In domain theory, what can the extra structure present in metric spaces be used for?

Smyth's chapter in the handbook of logic in computer science and other references describe how metric spaces can be used as domains. I do understand that complete metric spaces give unique fixed ...
Ben 's user avatar
  • 871
75 votes
14 answers
20k views

Applications of topology to computer science

I'd like to write a survey on the applications of Topology in Computer Science. I plan to cover the history of topological ideas in Computer Science and also highlight a few current developments. It ...
Ben 's user avatar
  • 871
16 votes
3 answers
1k views

Is the 3-sphere recognition problem NP-complete?

It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere is in NP, via work by Saul Schleimer in 2004: "Sphere recognition lies in NP" arXiv:math/0407047v1 [math.GT]. ...
Joseph O'Rourke's user avatar
28 votes
2 answers
662 views

Bounded-input bijections of infinite sequences

Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution. It is possible to define a bijection $ 3^\mathbb{N} \cong 5^\mathbb{N} $ ...
Colin McQuillan's user avatar
85 votes
20 answers
11k views

Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science. The best examples are those ...
4 votes
3 answers
600 views

What applications of Cantor space are there?

Are there well-established applications of the Cantor space ($2^\omega$) in computer science, other than those connected with computable real arithmetic? John Tucker's page Computation on Topological ...
Charles Stewart's user avatar