17

One connection is that graph isomorphism and knot isomorphism are both special cases of 3-manifold homeomorphism. In the knot case, two knots are isomorphic if their complements (manifolds formed by deleting the points of the knot from 3-space) are homeomorphic. And in the graph case it's possible to transform graphs into manifolds in such a way that the ...


7

the more general question is the connection between knot theory and graph theory. as one possible place to start there is a connection between the Jones polynomial (used to classify knots) and the Tutte polynomial of planar graphs. ie in knot theory, the Tutte polynomial appears as the Jones polynomial of an alternating knot. (so maybe there is some ...


7

The ideas the question expresses are interesting but maybe insufficiently fleshed out. I can see a couple of points that deserve further refinement. It is difficult to "code the exact same functionality". In part that is because what counts as "the exact same functionality" depends on the chosen notion of program equivalence. For terminating programs in ...


7

If there is an Arthur-Merlin protocol for knottedness similar to the [GMW85] and [GS86] Arthur-Merlin protocols for Graph Non Isomorphism, then I believe such a cryptocurrency proof-of-work could be designed, wherein each proof-of-work shows that two knots are not likely to be equivalent/isotopic. In more detail, as is well known in the Graph Non ...


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

here is a project Rosetta Code somewhat similar or adaptable to some of your goals [which as others point out are not very specific/objective/concise/clearcut yet], a database involving quantification of languages on the same task for comparison. the post "Code Length Measured in 14 Languages" is an example of the quantitative analysis possible with this ...


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$...


4

In Slide 26, Martin Escardo provides an algorithm that might give you what you're looking for: Go the library. Pick a book on topology. Pick a theorem. Apply the dictionary. Get a theorem in computation. http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf See also this paper


3

Some recent references here from Algebraic Topology, and UGC hardness- Morse Theory , and another reference Unique Games Conjecture and Computational Topology . The latter is about covering spaces of graphs, and "lifting" of graphs, and could point to a deeper link between Topology, and the Unique Games Conjecture.


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

Two big applications of homotopy theory in theoretical computer science are Homotopy Type Theory revealed a completely unexpected connection between the theory of the typed lambda calculus and homotopy theory. As a quick intuition, think of it as either a (vast) generalization of the connection between intuitionistic logic and topological spaces, or a ...


3

As someone somewhat familiar with termination analysis, I'd say that the techniques are only as ad-hoc as the programs they aim to prove termination of, which is to say very ad-hoc indeed. The crucial approach to scaling such analyses is modularity which allows decomposing the problem into sub-problems. Indeed this usually consists in identifying cycle-like ...


2

My answer to a related post: Applications for set theory, ordinal theory, infinite combinatorics and general topology in computer science?: The 2004 Gödel Prize was shared by the following two 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 ...


1

the Rosetta Code repository has been used for a new comprehensive scientific/ academic study of language succinctness among other comparisons of properties. announced at "Analyzing Programming Languages using Rosetta Code" A Comparative Study of Programming Languages in Rosetta Code Nanz/ Furia Sometimes debates on programming languages are more ...


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