Existem formulações teóricas de nó de problemas completos de NP?

Existem problemas completos de NP (ou mesmo NP-difícil ou NP) que possuem boas propriedades topológicas para estudar. Os problemas de PN têm formulações teóricas de nós? Sabemos sobre os resultados # sobre o polinômio de Jones. Problemas gráficos (incorporações?), Especificamente cores dos gráficos, podem ter boas propriedades teóricas dos nós. É uma pergunta em aberto e todas as referências a este tópico são bem-vindas. $P$

ct.category-theory np user3483902
fonte

Respostas:

Você pode dar uma olhada em:

Peter Golbus, Robert W. McGrail, Tomasz Przytycki, Mary Sharac e Aleksandar Chakarov. 2009. Os nós do toro tricolor são NP-completos . Atas da 47ª Conferência Regional Anual do Sudeste (ACM-SE 47). ACM, Nova York, NY, EUA, Artigo 42, 6 páginas.

Resumo: Este trabalho apresenta um método para associar uma classe de problemas de satisfação de restrições a um nó tridimensional. Dado um nó, pode-se construir um nó quandle, que geralmente é uma álgebra livre infinita. A coleção de problemas desejada é derivada do conjunto de relações invariantes sobre o nó quandle, aplicando a teoria que relaciona álgebras finitas a problemas de satisfação de restrições. Isso nos permite desenvolver noções de dilemas e nós tratáveis e completos com NP. Em particular, mostramos que todos os nós tricolores do toro e todos, exceto no máximo 2 nós não triviais com 10 ou menos cruzamentos são NP-completos.

e também ao seu relatório seminal:

P. Golbus, RW McGrail, M. Merling, K. Ober, M. Sharac e J. Wood. A classe de problemas de satisfação com restrições em um nó . Número do relatório técnico BARD-CMSC-2008-01, Bard College, 2008.

Marzio De Biasi
fonte

Existem algumas referências no primeiro parágrafo do

Marc Lackenby. Um limite superior polinomial em Reidemeister se move. arXiv: 1302.0180

Em particular, o autor diz que o problema de reconhecer que um diagrama de nó representa o nó está em , combinando um resultado de Hass-Lagarias-Pippenger (que o desconhecimento está em NP) com resultados independentes de Agol e Kuperberg (esse nó está em NP, este último provando isso sob a hipótese generalizada de Riemann). O resultado da Agol parece não ter sido publicado, mas as outras referências são: $\mathbf{NP} \cap \mathbf{coNP}$

Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. A complexidade computacional dos problemas de nós e vínculos. J. ACM 46 (1999) 185-211. arXiv: math / 9807016
Greg Kuperberg. O nó está em NP, módulo GRH. Dezembro de 2011, revisado em janeiro de 2014. arXiv: 1112.0845

Eu também encontrei outro artigo relacionado de Agol, Hass e Bill Thurston, onde eles mostram que o problema mais geral de determinar se um nó [em uma variedade múltipla fechada arbitrária] tem gênero no máximo é NP-completo: $g$

Ian Agol, Joel Hass e William Thurston. O NÚCLEO 3-MANIFOLD GENUS é NP-completo. STOC 2002. Link ACM

Também estou interessado em outros exemplos.

Noam Zeilberger
fonte

A prova co-NP nunca publicou de Agol usando hierarquias suturados é brevemente resumida em uma pesquisa recente da Lackenby: people.maths.ox.ac.uk/lackenby/ekt11214.pdf

Arnaud

E uma pequena precisão: a prova de dureza Agol, Hass, Thurston NP aplica-se apenas em 3 manifolds em geral, e não no gênero de nós em . Muito poucos resultados de dureza são conhecidos por problemas topológicos em e .

R^{3}

$\mathbb{R}^3$

R^{3}

$\mathbb{R}^3$

S^{3}

$\mathbb{S}^3$

Arnaud #

obrigado pela sua precisão: incluí-o no texto.

Noam Zeilberger

Talvez seja denso aqui, mas não está claro por que os resultados são caracterizados na resposta como falando de nó / inobservância "ser NP-difícil", em vez de "estar em NP", pois, tanto quanto posso ver em abstrato, eles afirmam que os problemas estão no NP, mas não que eles também sejam NP-Complete.

Abel Molina

não, você está certo, eu estava sendo denso. Corrigido agora.

Noam Zeilberger