Problemas com grandes lacunas de complexidade aberta

32

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 PA,BABAABBCACBPNP

Não estou interessado em problemas com e , porque ele já é o objeto desta pergunta .B = N PAPB=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 EAPBEXPTIMEPEXPTIME

Denis
fonte
O que você quer dizer com classes de um problema? Suponha que o problema seja SAT, como você define classes?
RB
O SAT é NP-completo, portanto podemos usar e não há nenhuma lacuna aqui, porque a complexidade do SAT corresponde exatamente a uma classe já conhecida. Mostrar qualquer novo resultado sobre a complexidade do SAT (pertencente a uma classe menor) seria um avanço na teoria da complexidade. A questão não é completamente bem definida, pois depende de quais classes de complexidade são consideradas "mainstream" e não são definidas de forma exclusiva. A questão específica, porém, é bem definida: exemplos de idiomas para os quais é coerente com o conhecimento atual que eles estejam em P ou EXPTIME-complete. A , BA=B=NPA,B
Denis
na verdade, ainda não está completamente bem definido por causa do "não colapso", portanto, ele se baseia em uma noção de "classe conhecida". Obviamente, um problema completo do PSPACE não se encaixa no requisito, embora estar em P ou EXPTIME-complete seja coerente com o conhecimento atual. Por exemplo, esta lista pode ser usada como referência para o que é uma classe "conhecida": en.wikipedia.org/wiki/List_of_complexity_classes
Denis
13
Isso não se encaixa perfeitamente no projeto de sua pergunta específica, mas, para todas as aparências, a teoria existencial dos reais resiste teimosamente a qualquer classificação além de ser NP-hard e dentro do PSPACE (o último resultado de JF Canny em 1988). en.wikipedia.org/wiki/Existential_theory_of_the_reals
anemone

Respostas:

28

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 n2cnc=10106n

Peter Shor
fonte
Obrigado pela sua resposta. Você conhece os limites atuais? Você pode apontar para uma referência informando o estado da arte atual? Estou tendo problemas para encontrar uma clara.
Denis
Eu tenho tentado encontrar algo mais recente do que o artigo de 1998 de Hass, Lagarias e Pippenger aqui . Isto afirma que o problema de equivalência de nós é conhecido por ser decidível. Eu não ficaria surpreso se alguém tivesse mostrado que estava em EXPTIME desde então, mas não acredito em nada melhor do que aquilo que é conhecido, e certamente não está claro que não esteja em P. Tenho certeza de que nenhum dos resultados que mostram que decidir se algo é atado está em NP se estendem a esse problema mais geral.
Peter Shor
Esta pergunta do MO está relacionada: mathoverflow.net/questions/77786/… Em particular, usando resultados recentes anunciados por Lackenby em people.maths.ox.ac.uk/lackenby/ekt11214.pdf , obtém-se isso para qualquer tipo de nó K, determinar se um determinado nó é equivalente a K está em NP (nota que este não melhorar no nó Equivalência Problema)
Arnaud
@Arnaud: na verdade, parece-me que esses resultados provam que, para dois diagramas com no máximo n cruzamentos, o problema de equivalência de nós pode ser resolvido no tempo, no máximo, com uma torre de 2s de altura , onde é uma enorme constante. Eu deveria verificar isso e editar minha resposta. ccnc
Peter Shor 27/02
@ PeterShor Sim, de fato. Eu estava focando no resultado mais recente, porque ele pode levar a um limite aprimorado quando é publicado, se o polinômio real for explicitado.
Arnaud
23

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 / 22n2n/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 redução uniforme de NC0 de PARITY para MCSP.N P N P A C 0 [ 2 ]AC0NPNPAC0[2]

Ryan Williams
fonte
23

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 02PPPPPPPBitSLPnAC0

SamiD
fonte
21

Outro problema topológico natural, semelhante em espírito à resposta de Peter Shor, é a capacidade de incorporar complexos simplais abstratos bidimensionais emR3 . 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=3kRdk=1d=2k=2d=2k=2d=3demonstrado 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.

Sasho Nikolov
fonte
16

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.

Thomas S
fonte
3
Olá Thomas, há uma alegação de um limite superior de complexidade explícita (e provavelmente não muito restrita) em um artigo recente do arXiv: arxiv.org/abs/1503.00745 . A proposta de limite superior em é, contudo, muito além das classes de complexidade o cartaz original foi interessado.Fω3
Sylvain
@Sylvain Cool! Obrigado por compartilhar isso. :)
Michael Wehar
@Sylvain EXPTIME é o limite inferior mais conhecido?
Michael Wehar
2
@ Michael: o melhor limite inferior para o problema de decisão é EXPSPACE (Lipton, 1976, cpsc.yale.edu/sites/default/files/files/tr63.pdf ). Contudo, o algoritmo de Mayr (1981, dx.doi.org/10.1145/800076.802477 ), Kosaraju (1982, dx.doi.org/10.1145/800070.802201 ) e Lambert (1992, dx.doi.org/10.1016/0304- Sabe-se que 3975 (92) 90173-D ) analisada no artigo arXiv mencionado requer pelo menos tempo Ackermanniano (isto é, ). Fω
214 Sylvain
@Sylvain Muito obrigado por todas as informações adicionais. Eu realmente gostei disso. :)
Michael Wehar
11

Q M A N E X PQMA(2) (Quantum Merlin-Arthur com dois provadores não enredados): certamente -hard, mas conhecido apenas por . QMANEXP

Martin Schwarz
fonte
9

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 PEXPSPACEPP

Joshua Grochow
fonte
Você pode fornecer mais informações sobre isso de forma explícita? parece algum tipo de problema bpp-complete?
@Arul: Nem o PIT nem esse problema são BPP-completos em nenhum sentido que eu saiba. (De fato, mostrar que existem problemas completos de BPP ainda está aberto e requer técnicas de não relativização - um resultado que remonta a Sipser.) No entanto, a desaerocialização ou tem uma troca de dureza-aleatoriedade, na medida em que sua deserandomização é essencialmente equivalente para baixar limites. Além do artigo vinculado na resposta ("GCT 5"), procure dureza-aleatoriedade e Kabanets-Impagliazzo.
Joshua Grochow 18/10/2015
Eu vou fazer isso, mas eu estava interessado nesta frase 'e, na verdade, seu ser em P é essencialmente equivalente a derandomizing PIT', que parece dizer PIT é uma espécie de procuração completa problema
@Arul: Sim, para ver por que o PIT é um "problema de proxy completo", veja as coisas a que me referi no meu comentário anterior.
Joshua Grochow
por que ele usa 'Dedicado a Sri Ramakrishna' em muitas de suas obras?
6

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.

David Eppstein
fonte