Problemas com grandes lacunas de complexidade aberta

Esta pergunta é sobre problemas para os quais existe uma grande lacuna de complexidade aberta entre o limite inferior e o limite superior conhecidos, mas não devido a problemas abertos nas próprias classes de complexidade.

Para ser mais preciso, digamos que um problema tenha classes de lacunas (com , não definido exclusivamente) se for uma classe máxima para a qual podemos provar que é -hard, e é um valor mínimo mínimo conhecido. ligado, ou seja, temos um algoritmo em resolvendo o problema. Isso significa que, se descobrirmos que o problema é completo com , isso não afetará a teoria da complexidade em geral, em vez de encontrar um algoritmo para um completo.A ⊆ B A A B B C A ⊆ C ⊆ B P N $A,B$$A\subseteq B$$A$$A$$B$$B$$C$$A\subseteq C\subseteq B$$P$$NP$

Não estou interessado em problemas com e , porque ele já é o objeto desta pergunta .B = N $A\subseteq P$$B=NP$

Estou procurando exemplos de problemas com classes de diferença o mais longe possível. Para limitar o escopo e precisar a pergunta, estou especialmente interessado em problemas com e , o que significa que a participação em e -completeness são coerentes com o conhecimento atual, sem causar o colapso de classes conhecidas (por exemplo, classes de esta lista ).B ⊇ E X P T I M E P E X P T I M $A\subseteq P$$B\supseteq EXPTIME$$P$$EXPTIME$

O problema da equivalência de nós .

Dados dois nós desenhados no avião, eles são topologicamente iguais? Sabe-se que esse problema é decidível e não parece haver nenhuma obstrução da complexidade computacional em P. O melhor limite superior atualmente conhecido em sua complexidade temporal parece ser uma torre de s de altura , onde e é o número de cruzamentos nos diagramas de nós. Isso vem de um limite de Coward e Lackenby sobre o número de movimentos de Reidemeister necessários para dar um nó a um equivalente. Veja o artigo mais recente de Lackenby para obter alguns resultados relacionados mais recentes e a forma explícita do limite que forneço acima (página 16).c n c = 10 10 6$2$$c^n$$c = 10^{10^{6}}$$n$

Aqui está uma versão do problema de tamanho mínimo de circuito (MCSP): dada a tabela verdade de bits de uma função booleana, ela possui um circuito de tamanho no máximo ?2 n /$2^n$$2^{n/2}$

Conhecido por não estar em . Contido em . Geralmente acredita-se ser duro, mas isso está aberto. Acredito que nem se sabe que seja -hard. De fato, trabalhos recentes com Cody Murray (a aparecer no CCC'15) mostram que não há redução uniforme de NC0 de PARITY para MCSP.N P N P A C 0 [ 2 $AC0$$NP$$NP$$AC0[2]$

A complexidade de calcular um bit (especificado em binário) de um número algébrico irracional (como ) tem o limite superior mais conhecido de através de uma redução no problema que sabia ter esse limite superior [ABD14] . Por outro lado, nem sabemos se esse problema é mais difícil do que calcular a paridade de bits - pois sabemos que esse problema pode estar em . Observe, no entanto, que sabemos que nenhum autômato finito pode calcular os bits de um número algébrico irracional [AB07] P P P P P P P B i t S L P NA C $\sqrt{2}$$\mathsf{P^{{{PP}^{PP}}^{PP}}}$$\mathsf{BitSLP}$$n$$\mathsf{AC^0}$

Outro problema topológico natural, semelhante em espírito à resposta de Peter Shor, é a capacidade de incorporar complexos simplais abstratos bidimensionais em$\mathbb{R}^3$ . Em geral, é natural perguntar quando podemos efetivamente / eficientemente decidir que um complexo simplicial abstrato dimensional pode ser incorporado em . Para e isto é a planaridade gráfico problema e tem um algoritmo de tempo linear. Para e , há também um algoritmo de tempo linear . O caso , estava aberto até o ano passado, quando foi k R dk=1d=2k=2d=2k=2d=3$k$$\mathbb{R}^d$$k=1$$d=2$$k=2$$d=2$$k=2$$d=3$demonstrado ser decidido por Matousek, Sedgwick, Tancer e Wagner . Eles dizem que seu algoritmo tem um tempo recursivo primitivo , mas maior que uma torre de exponenciais . Por outro lado, especulam que pode ser possível colocar o problema em NP, mas ir além disso seria um desafio. No entanto, não parece haver nenhuma evidência forte de que um algoritmo polytime seja impossível.

Este último artigo tem muitas referências para leitura adicional.

Os autômatos multicounter (MCAs) são autômatos finitos equipados com contadores que podem ser incrementados e decrementados em uma etapa, mas apenas números inteiros> = 0 como números. Diferentemente das máquinas Minsky (também conhecidas como contra-autômatos), as MCAs não têm permissão para testar se um contador é zero.

Um dos problemas algorítmicos com uma enorme lacuna relacionada às MSCs é o problema de alcançabilidade. Por exemplo, se o autômato pode alcançar, a partir de uma configuração com o estado inicial e todos os contadores zero, uma configuração com um estado de aceitação e todos os contadores zero novamente.

O problema é difícil para EXPTIME (como mostrado por Richard Lipton em 1976), decidível (Ernst Mayr, 1981) e solucionável em Fω3 (obrigado, Sylvain, por apontar isso). Uma enorme lacuna.

Q M A N E X $\mathsf{QMA}(2)$ (Quantum Merlin-Arthur com dois provadores não enredados): certamente -hard, mas conhecido apenas por . $\mathsf{QMA}$$\mathsf{NEXP}$

O problema computacional associado ao lema de normalização de Noether para variedades explícitas ("explícito" no sentido deste artigo [ versão completa disponível gratuitamente ]). O limite superior mais conhecido é (observe ESPAÇO, NÃO TEMPO!), Mas é conjecturado como estando em (e, de fato, estar em é essencialmente equivalente a desalinhar o PIT) .P $\mathsf{EXPSPACE}$$\mathsf{P}$$\mathsf{P}$

O problema de Skolem (dada uma recorrência linear com casos base inteiros e coeficientes de número inteiro, atinge o valor 0) é conhecido por ser NP-difícil e não por ser decidível. Tanto quanto sei, qualquer coisa entre elas seria consistente com nosso conhecimento atual, sem colapsos das classes de complexidade padrão.