Por que tão poucos candidatos naturais ao status intermediário de NP?

29

É bem conhecido pelo Teorema de Ladner que se , então existem infinitas N P Intermédio ( N P I problemas). Também existem candidatos naturais para esse status, como Isomorfismo em grafos, e vários outros, consulte Problemas entre P e NPC . No entanto, a vasta maioria no multidão de conhecida n um t u r a L N P -Problemas são conhecidos por ser tanto em P ou N P C . Apenas uma pequena fração deles permanece candidata a N P IPNPNPNPInatural NPPNPCNPI. Em outras palavras, se escolher aleatoriamente um naturais -problem entre os conhecidos, temos muito pouca chance de escolher um N P I candidato. Existe alguma explicação para esse fenômeno?NPNPI

Eu poderia pensar em 3 explicações possíveis, mais no lado filosófico:

  1. A razão para se ter uma pequena fracção de tais naturais de candidatos que é N P I irá eventualmente vir a estar vazio. Eu sei, isso implica P = N P , então é muito improvável. No entanto, um ainda pode-se argumentar (embora não tenho um deles) que a raridade de naturais N P I problemas é uma observação empírica de que aparece para efectivamente suportar P = N P , em contraste com a maioria das outras observações.NPINPIP=NPNPIP=NP

  2. A pequenez do "natural- " representa um tipo de transição de fase aguda entre problemas fáceis e duras. Aparentemente, os problemas algorítmicos naturais significativos e comportam-se de uma maneira que tendem a ser fáceis ou difíceis, a transição é estreita (mas ainda existe).NPI

  3. O argumento em 2 pode ser levado ao extremo: eventualmente, todos os problemas em "natural- " será colocado em PN P C , ainda PN P , de modo N P I . Isso significaria que todos os problemas restantes em N P INPIPNPCPNPNPINPIsão "não naturais" (artificial, sem significado na vida real). Uma interpretação disso pode ser que os problemas naturais são fáceis ou difíceis; a transição é apenas uma construção lógica, sem significado "físico". Isso lembra um pouco os números irracionais, que são perfeitamente lógicos, mas não surgem como o valor medido de qualquer quantidade física. Como tal, eles não provêm da realidade física, estão antes no "fechamento lógico" dessa realidade.

Qual explicação você mais gosta ou pode sugerir outra?

Andras Farago
fonte
13
Hum, o comprimento da diagonal de um quadrado 1 centímetro x 1cm é um número irracional ...
Joshua Grochow
4
Você também pode achar interessante que, na teoria da medida limitada a recursos, a coleção de conjuntos completos de NP tenha uma medida p 0. Em outras palavras, conjuntos aleatórios de p em NP não são completos em NP. De fato, isso é verdade para qualquer grau polinomial de tempo múltiplo. (A medida da coleção de todos os conjuntos de NP é uma questão em aberto: se for diferente de zero ou não mensurável, então ) #PNP
2100 Joshua Grochow
7
a resposta tem a ver principalmente com os problemas que consideramos "naturais", que é uma questão bastante filosófica. também não está muito claro que a premissa da pergunta se mantém: muitos problemas decorrentes da criptografia têm complexidade intermediária. finalmente, o que você está dizendo sobre números irracionais é absurdo.
Sasho Nikolov

Respostas:

26

Como outros já apontaram, é discutível até que ponto a coisa que você está tentando explicar é verdadeira. Pode-se argumentar que, nas décadas de 60 e 70, os cientistas teóricos da computação estavam apenas mais interessados nos tipos de problemas que acabam sendo em P ou em NP completos. Hoje, devido ao aumento da criptografia teórica da complexidade, da computação quântica, das redes, etc. -, bem como do simples fato de que a completude do NP se tornou tão bem compreendida - nos tornamos cada vez mais interessados ​​em os tipos de problemas que acabam sendo intermediários em NP.

Ainda assim, pode-se perguntar: na medida em que a coisa é verdadeira - ou seja, na medida em que tantos problemas naturais de pesquisa e otimização "se encaixam" em serem NP completos ou em P --- até esse ponto , porque é verdade? Aqui, acho que você pode obter muita intuição observando um fenômeno anterior da computabilidade: que tantos modelos naturais de computação "se encaixam" em se tornarem completos em Turing. Nesse caso, eu diria que a explicação é que, uma vez que você tenha alguns componentes básicos - uma memória de leitura / gravação, loops, condicionais, etc. - é difícil evitarser capaz de simular uma máquina de Turing e, portanto, estar completo com Turing. Da mesma forma, uma vez que seu problema de pesquisa ou otimização possui alguns componentes básicos - mais importante, a capacidade de construir "gadgets" que imitam portas lógicas como AND, OR e NOT - é difícil evitar para codificar SAT e, portanto, sendo NP-completo.

Do jeito que eu gosto de pensar sobre isso, problemas como o SAT exercem uma poderosa "força gravitacional" sobre todos os outros problemas computacionais próximos, fazendo com que eles também desejem "se acostumar" a serem NP-completos. Portanto, normalmente nem exige explicação especial quando outro problema sucumbe a essa atração! O mais impressionante e mais necessitado de explicação é quando um problema NP (aparentemente) difícil tem alguma propriedade que permite resistir à atração gravitacional do SAT. Queremos saber: o que é essa propriedade? Por que você não pode usar o truque usual de completude de NP para esse problema, de construir gadgets que codificam portas lógicas booleanas? Fiz uma lista de algumas respostas comuns a essa pergunta nesta recente resposta do CS.SE, mas (como outro comentarista já apontou), há outras respostas possíveis que eu perdi.

Scott Aaronson
fonte
Também relevante para a última parte é a pergunta de Scott cstheory.stackexchange.com/questions/19256/…
András Salamon
17

Muitos problemas naturais podem ser expressos como problemas de satisfação de restrições e existem teoremas de dicotomia para CSPs.

Joshua Grochow
fonte
9

Apenas uma piada: depois de pensar na "força gravitacional do SAT" na bela resposta de Scott Aaronson, outra metaphore me veio à mente: o sanduíche 3-SAT 2-SAT !

insira a descrição da imagem aqui



... mas não sei se o sanduíche pode ser preenchido com ingredientes naturais (no entanto, achei que poderia ser preenchido com alguns -SAT sauce [1] se a hipótese de tempo exponencial for verdadeira) :-D(2+(logn)kn2)

Outro resultado em [1] é que ele não pode ser preenchido com .(2+1/n2ϵ),0<ϵ<2

[1] Yunlei Zhao, Xiaotie Deng, CH Lee, Hong Zhu, -SAT e suas propriedades(2+f(n)) , Matemática Aplicada Discreta, Volume 136, Edição 1, 30 de janeiro de 2004, Páginas 3-11, ISSN 0166 -218X.

Marzio De Biasi
fonte
3
No entanto, não pode ser preenchido com -SAT: eccc.hpi-web.de/report/2013/159(2+ε)
Joshua Grochow
@ JoshuaGrochow: minha referência para o "molho" é o artigo Zhao, Deng, Lee e Zhu " (2+f(n)) -SAT e suas propriedades" eles também provaram que ele não pode ser preenchido com ... Vou dar uma olhada no papel ( 2 + ϵ ) -SAT (eu apenas o abri e é estranho que eles não tenham colocado Zhao et al. suas referências)(2+1/n2ϵ),0<ϵ<2(2+ϵ)
Marzio De Biasi
3
As definições de -SAT nos dois artigos são diferentes; Eu acho que ambos estão corretos! (2+f(n))
Joshua Grochow
11
@MarzioDeBiasi, você deve considerar adicionar essas duas referências diretamente à sua resposta (onde são pesquisáveis) em vez de ocultá-las nos comentários.
Artem Kaznatcheev
8

Não podemos descartar-out uma possibilidade diante de que há uma abundância de naturais problemas Intermédio. A escassez aparente é devido à falta de técnicas e ferramentas necessárias necessária para provar N P estado Intermédio sob alguma complexidade conjectura plausível (Arora e Barak notar-se que não se pode provar que o N P estado Intermédio de qualquer naturais N P problema, mesmo assumindo P ( N P ).NPNPNPNPPNP

Parece que as comportas de naturais problemas Intermédio estão abertos. Jonsson, Lagerkvist e Nordh estenderam a técnica de diagonalização de Ladner, conhecida como abrir buracos nos problemas , e aplicaram-na a problemas de satisfação de restrições. Eles obtiveram uma CSP que é um candidato para N P estado Intermédio. Provaram que problema abdução proposicional tem N P fragmentos Intermédio.NPNPNP

Além disso, Grohe provou a existência de problemas CSP Intermédio supondo que F P T W [ 1 ] . Ele obteve tais problemas restringindo a largura da árvore dos correspondentes gráficos primários.NPFPTW[1]

Referências :

1- M. Grohe. A complexidade do homomorfismo e os problemas de satisfação de restrições vistos do outro lado. Revista da ACM, 54 (1), artigo 1, 2007

2- Peter Jonsson, Victor Lagerkvist e Gustav Nordh. Explodindo Buracos em Vários Aspectos de Problemas Computacionais, com Aplicações para Restringir Satisfação. Em Anais da 19ª Conferência Internacional sobre Princípios e Práticas de Programação de Restrições (CP-2013). 2013.

Mohammad Al-Turkistany
fonte
11
por que esses problemas de CSP não se enquadram na conjectura de dicotomia?
Sasho Nikolov 08/02
11
Restringir a largura da árvore como no resultado de Grohe é realmente natural? (A questão não é retórica - sinceramente não sei.) Na minha opinião, as construções de Johnsson-Lagerkvsit-Nordh parecem apenas um pouco mais naturais que as de Ladner. Penso que o ponto do seu primeiro parágrafo é excelente.
Joshua Grochow
@ JoshuaGrochow Tenho medo de que seja discutível, pois não há noção formal do que significa natural .
Mohammad Al-Turkistany
@SashoNikolov Você quer dizer a conjectura de dicotomia de Feder e Vardi?
Mohammad Al-Turkistany
11
@ MohammadAl-Turkistany: Não vejo contradição. O JLN constrói explicitamente classes de instâncias que não estão no formato CSP ( , _ ) ou CSP ( _ , B ), portanto, evitam as dicotomias conhecidas. Veja também o par anterior de artigos de Chen-Thurley-Weyer e Bodirsky-Grohe para idéias semelhantes. A__B
András Salamon
7

Aqui está um conto de fadas sobre a estrutura dos Cachinhos Dourados dos problemas intermediários de NP. (Atenção: essa história pode ser uma falácia útil para gerar e testar hipóteses em potencial, mas não deve ser cientificamente rigorosa. Ela se baseia em uma parte da Hipótese do tempo exponencial, uma pitada da magia da complexidade de Kolmogorov, algumas peças emprestadas da teoria do SAT resolução de problemas e a tricotomia heurística de Terence Tao para problemas. Consuma por sua conta e risco, como em todas as misturas de matemática que acenam com a mão.)

Se quase todas as instâncias de um problema no NP são altamente estruturadas, o problema está realmente em P. As instâncias, portanto, quase todas contêm muita redundância, e um algoritmo de tempo polinomial para o problema é uma maneira de fatorar a redundância. É até concebível que todo problema em P possa ser obtido pegando algum problema no EXP e adicionando alguma redundância estruturada, através de alguma forma de preenchimento (não necessariamente do tipo usual). Se assim fosse, um algoritmo de tempo polinomial poderia ser visto como uma maneira eficiente de desfazer esse preenchimento.

Se houver instâncias suficientes que não estão estruturadas, formando um "núcleo de dureza", o problema é NP-completo.

No entanto, se esse "núcleo de dureza" for muito escasso, ele só terá espaço para representar parte do SAT; portanto, o problema está no intermediário P ou NP. (Este argumento é a essência do teorema de Ladner). Para usar a analogia de Scott, o "núcleo da dureza" exerce uma força gravitacional sobre o problema, em direção a ele estar completo como NP. As instâncias no "núcleo da dureza" não contêm muita redundância, e o único algoritmo realista que funciona para todas essas instâncias é a pesquisa de força bruta (é claro, se houver apenas finitas, a pesquisa de tabela também funcionará).

Nesta perspectiva, os problemas intermediários de NP devem ser raros na prática, uma vez que exigem um bom equilíbrio de Goldilocks entre instâncias estruturadas e não estruturadas. As instâncias devem ter redundância suficiente para serem parcialmente acessíveis a um algoritmo, mas deve haver um núcleo de dureza suficiente para que o problema não esteja em P.


Pode-se contar uma história ainda mais simples (e divertida, mas também potencialmente ainda mais enganosa) baseada em quebra-cabeças. Com apenas algumas restrições, é possível forçar muita pesquisa a ser feita, por exemplo, o NxN Sudoku é NP-complete. Agora considere ser solicitado a resolver muitos quebra-cabeças pequenos como uma única instância, de uma só vez (por exemplo, muitos Sudokus 9x9). O tempo gasto será aproximadamente linear no número de quebra-cabeças em cada instância, e esse problema estará em P. Para problemas intermediários, pode-se pensar em cada instância como um número muito grande (mas não muito grande) de Sudokus em grande quantidade. (mas não muito grandes). A razão pela qual não observamos muitos desses problemas é porque eles seriam tristes de posar e resolver!

András Salamon
fonte
11
LCLknk+kCLPL) levantam a hipótese de que os idiomas no NP com núcleos suficientemente densos precisam estar completos no NP.
11602 Joshua Grochow
11
As referências que Joshua mencionou: Lynch: dx.doi.org/10.1145/321892.321895 e Orponen-Schöning: dx.doi.org/10.1016/S0019-9958(86)80024-9 também ver Orponen-Ko-Schöning-Watanabe: dx. doi.org/10.1145/174644.174648
András Salamon
2

NPINPINP problemas -Complete. O argumento poderia ser o seguinte.

nlognNPI NPxQxQNPEuP , como a mera restrição de tamanho provavelmente não introduz nova estrutura.

NPEuNPNPEuNPC . "

NPEuP

Andras Farago
fonte
3
W[1 1]
xQxO(log|x|)
Para 3-COLORING, qual é a versão reduzida do problema?
András Salamon
11
nregistron
2
Não é a diferença entre "ser uma camarilha" e "ser de três cores". É a diferença entre o problema original: 1) um gráfico possui um subgrafo com alguma propriedade de um determinado tamanho (por exemplo, CLIQUE) vs. 2) um gráfico possui uma propriedade. No caso de (1), mudar o tamanho para ser logarítmico é natural, porque o tamanho do subgráfico já fazia parte da questão. Quando você faz o truque para (2), adiciona o tamanho do subgráfico como uma nova parte do problema.
Joshua Grochow