Técnicas para mostrar que o problema está na dureza "limbo"

36

Dado um novo problema em cuja verdadeira complexidade está em algum lugar entre e sendo NP-complete, existem dois métodos que eu conheço que podem ser usados ​​para provar que resolver isso é difícil:PNPP

  1. Mostre que o problema é GI-completo (GI = Isomorfismo do gráfico)
  2. Mostre que o problema está em . Pelos resultados conhecidos, esse resultado implica que, se o problema for NP-completo, o PH entrará em colapso para o segundo nível. Por exemplo, o famoso protocolo para Nonisomorphism Graph faz exatamente isso.coAM

Existem outros métodos (talvez com diferentes "pontos fortes da crença") que foram usados? Para qualquer resposta, é necessário um exemplo de onde ele realmente foi usado: obviamente existem muitas maneiras de tentar mostrar isso, mas os exemplos tornam o argumento mais convincente.

Suresh Venkat
fonte
12
Se um problema parecer difícil o suficiente, mas você não conseguir provar que é NPC, uma verificação rápida é contar o número de cadeias de comprimento n no idioma: se o conjunto for escasso, é improvável que seja NPC (caso contrário, P = NP pelo teorema de Mahaney) ... então é melhor direcionar esforços para provar que ele está em P :-) :-) Um exemplo do blog da Fortnow & Gasarch : {(n, k): existe uma maneira de particionar { 1, ..., n} para a maioria das caixas de k de modo que nenhuma caixa tem x, y, z com x + y = z}
Marzio De Biasi
5
@MarzioDeBiasi parece uma resposta para mim.
Sasho Nikolov 06/02
2
Há duas partes nessa demonstração: mostrar a dificuldade de colocar o problema no BPP e mostrar a dificuldade de colocar o problema na classe NP-complete. (Lembre-se de que a completude do IG significa apenas "está no IG e é difícil para o IG".)
1
+1 para Ricky Demer; podemos querer ter uma lista de métodos para a primeira parte.
Pteromys
2
Para problemas no FNP sem versões óbvias de decisão no NP, o PPAD é uma classe útil (e crescente) a ser considerada. Os problemas completos do PPAD incluem muitos problemas para encontrar pontos fixos, por exemplo, equilíbrios de Nash. A lista de Shiva é útil: cs.princeton.edu/~kintali/ppad.html
András Salamon

Respostas:

47

Mostrar que seu problema está no coAM (ou SZK) é realmente uma das principais maneiras de gerar evidências para o "limbo da dureza". Mas além disso, existem vários outros:

  • Mostre que seu problema está no NP ∩ coNP. (Exemplo: Factoring.)
  • Mostre que seu problema é solucionável em tempo quase-polinomial. (Exemplos: dimensão VC, aproximando jogos gratuitos.)
  • Mostre que seu problema não é mais difícil do que inverter funções unidirecionais ou resolver o NP em média. (Exemplos: muitos problemas em criptografia.)
  • Mostre que o seu problema se reduz a (por exemplo) Jogos exclusivos ou Expansão em conjuntos pequenos.
  • Mostre que seu problema está no BQP. (Exemplo: fatoração, embora é claro que também esteja no NP ∩ coNP.)
  • Descartar grandes classes de reduções de completude de NP. (Exemplo: O Problema de Minimização de Circuitos, estudado por Kabanets e Cai.)

Tenho certeza de que há outras que estou esquecendo.

Scott Aaronson
fonte
2
Essa é uma excelente lista, Scott!
Suresh Venkat
1
Apenas curioso ... qual dessas técnicas mostra que é improvável que o problema seja solucionável em tempo polinomial (ou RP ou BPP)? Não vi nada que parecesse fazer isso.
Philip White
2
Philip: Você está certo, eles não. Para fornecer evidências de que um problema específico de PN não está em P, tudo se resume a (1) tentar colocá-lo em P e falhar e / ou (2) reduzir outros problemas que as pessoas não colocaram em P para esse problema.
Scott Aaronson
23

Pelo comentário acima: se um problema parecer difícil o suficiente, mas você não conseguir provar que é NP-completo, uma verificação rápida é para contar o número de cadeias de comprimento no idioma: se o conjunto for escasso, é improvável que seja NPC, caso contrário P = NP pelo teorema de Mahaney ... então é melhor direcionar esforços para provar que ele está em P :-) :-)n

Um exemplo é o problema de particionar números em k-boxes (do blog da Fortnow & Gasarch, fonte original: Cyberpuzzles do Doctor Ecco ):

{ 1 , . . . , n }  em no máximo k caixas para que nenhuma caixa tenha  x , y , z  com  x + y = z }{(n,k) existe uma maneira de particionar  {1,...,n} em no máximo k caixas para que nenhuma caixa tenha x,y,z com x+y=z}

Marzio De Biasi
fonte
23

Aqui estão três adições à lista de Scott:

  • Mostre que seu problema está em alguns pontos. Isso significa que o número de soluções é limitado por algum polinômio. (Exemplo: problema do turnpike). Sabe-se que nenhum problema de NP-completo está em poucosP. (impossível a menos que P = NP).
  • euOGNPNP[euog2n]
  • 2nϵNPϵ>0 0n0 02nϵn

coNPNP/poeuy

Mohammad Al-Turkistany
fonte
1
Ou até em UP (e não apenas no FewP)!
Joshua Grochow 07/02