Complexidade das propriedades topológicas.

Eu sou um cientista da computação fazendo um curso de Topologia (uma pitada de topologia de conjunto de pontos fortemente aromatizada pela teoria do continuum). Interessei-me por problemas de decisão testando uma descrição de um espaço (por simplicidades) para propriedades topológicas; aqueles preservados até o homeomorfismo.

Sabe-se, por exemplo, que a determinação do gênero de um nó está no PSPACE e é NP-Hard. (Agol 2006; Hass, Lagarias, Pippenger 1999)

Outros resultados têm mais uma sensação mais geral: AA Markov (filho do Markov) mostraram em 1958 que testar dois espaços para um homeomorfismo em dimensões ou superior é indecidível (mostrando a indecidibilidade para 4-manifolds). Infelizmente, este último exemplo não é um exemplo perfeito da minha pergunta, pois lida com o problema da homeomorfia em si, e não com as propriedades preservadas pelo homeomorfismo.$5$

Parece haver uma grande quantidade de trabalho em "topologia de baixa dimensão": teoria dos nós e dos grafos. Definitivamente, estou interessado nos resultados da topologia de baixa dimensão, mas estou mais interessado nos resultados generalizados (estes parecem ser raros).

Estou mais interessado em problemas que são NP-Hard em média, mas me sinto encorajado a listar problemas que não são conhecidos por isso.

Quais resultados são conhecidos sobre a complexidade computacional das propriedades topológicas?

A topologia computacional abrange um enorme corpo de pesquisa. Um resumo completo de todos os resultados de complexidade seria impossível. Mas, para provar um pouco, deixe-me expandir seu exemplo.

$O(n)$

Em 1950, Turing provou que a palavra problema em semigrupos finitamente apresentados é indecidível, pela redução do problema da parada (surpresa, surpresa).

Com base no resultado de Turing, Markov provou em 1951 que toda propriedade não trivial de semigrupos com apresentação finita é indecidível. Uma propriedade de grupos não é trivial se algum grupo tiver a propriedade e outro não. Os cientistas teóricos da computação sabem o resultado semelhante sobre funções parciais como o "Teorema de Rice".

Em 1952, Novikov provou que o problema da palavra em finitamente apresentados grupos é indecidível, provando assim que a intuição de Dehn estava correta. O mesmo resultado foi provado independentemente por Boone em 1954 e Britton em 1958.

Em 1955, Adyan provou que cada propriedade não trivial de finitamente apresentados grupos é indecidível. O mesmo resultado foi provado de forma independente por Rabin em 1956. (Sim, esse Rabin.)

Finalmente, em 1958, Markov descreveu algoritmos para construir complexos celulares bidimensionais e coletores quadridimensionais com qualquer grupo fundamental desejado, considerando a apresentação do grupo como entrada. Esse resultado implicou imediatamente que um grande número de problemas topológicos é indecidível, incluindo o seguinte:

• Um determinado ciclo em um dado complexo bidimensional é contratável? (Esse é o problema da palavra.)
• Um determinado complexo 2 está simplesmente conectado? ("Este grupo é trivial?")
• Um dado ciclo em um determinado 4-coletor é contratável?
• Um determinado 4-coletor é contratável?
• Um dado 4-manifold é homeomórfico para um determinado 4-manifold (construído por Markov)?
• Um dado coletor 5 é homeomórfico para a esfera 5 (ou qualquer outro coletor 5 fixo que você escolher)?
• Um determinado complexo 6 ​​é uma variedade?

$G$$G$$\pi_1(S^3)$$G$$G$

Ryan Budney iniciou discussões semelhantes no MathOverFlow:

/mathpro/35946/how-expensive-is-knowledge-knots-links-3-and-4-manifold-algorithms

/mathpro/144158/what-is-the-state-of-the-art-for-algorithmic-knot-simplification/145927

e na Wikipedia:

http://en.wikipedia.org/wiki/Talk:Computational_topology