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.
40 questions
9
votes
1
answer
271
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 ...
- 101
3
votes
1
answer
140
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 ...
8
votes
1
answer
435
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-...
- 91
2
votes
2
answers
482
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-...
3
votes
0
answers
91
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 ...
5
votes
0
answers
199
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 ...
- 920
6
votes
2
answers
522
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. .
...
- 1,261
2
votes
1
answer
143
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 ...
- 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 ...
- 171
11
votes
0
answers
220
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 ...
- 32.9k
5
votes
1
answer
141
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 ...
- 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 ...
- 111
5
votes
0
answers
132
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$ ...
9
votes
0
answers
341
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 ...
- 785
0
votes
0
answers
154
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 ...
- 163
10
votes
2
answers
419
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 ...
- 2,314
16
votes
3
answers
721
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 ...
- 263
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 ...
- 473
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/...
- 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 ...
- 1,542
6
votes
2
answers
584
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 ...
- 1,671
8
votes
3
answers
606
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 ...
- 32.2k
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....
- 367
3
votes
1
answer
493
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 ...
user1338
1
vote
1
answer
456
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 ...
- 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 \...
- 2,057
19
votes
1
answer
317
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 ...
- 431
2
votes
0
answers
142
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 ...
- 121
7
votes
2
answers
229
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 ...
- 113
0
votes
1
answer
314
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' ...
- 69
19
votes
1
answer
855
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}} \...
5
votes
1
answer
552
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 ...
- 151
1
vote
1
answer
219
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? ...
- 1,671
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 ...
- 2,055
12
votes
1
answer
479
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 ...
- 891
77
votes
14
answers
21k
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 ...
- 891
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].
...
- 3,773
28
votes
2
answers
667
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} $ ...
- 3,606
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
627
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 ...
- 4,306