Intratabilidade de problemas NP-completos como um princípio da física?

Fico sempre intrigado com a falta de evidências numéricas da matemática experimental a favor ou contra a questão P vs NP. Embora a hipótese de Riemann possua algumas evidências de apoio da verificação numérica, não conheço evidências semelhantes para a pergunta P vs NP.

Além disso, não conheço nenhuma conseqüência direta do mundo físico da existência de problemas indecidíveis (ou da existência de funções incontestáveis). A dobragem de proteínas é um problema NP-completo, mas parece estar ocorrendo com muita eficiência em sistemas biológicos. Scott Aaronson propôs o uso da NP Hardness Assumption como um princípio da física. Ele declara a suposição informalmente como " problemas completos de NP são intratáveis ​​no mundo físico ".

Assumindo a suposição de dureza NP, Por que é difícil projetar um experimento científico que decida se nosso universo respeita a suposição de dureza NP ou não?

Além disso, existe alguma evidência numérica conhecida da matemática experimental a favor ou contra ?$P\ne NP$

EDIT: Aqui está uma bela apresentação de Scott Aaronson intitulada Intratabilidade computacional como uma lei da física

Eu não acho que o fato de ser uma afirmação assintótica seja um "desagregador" automático. Pode-se fazer conjecturas concretas que são consistentes com nosso conhecimento, mas mais fortes que P vs NP, como "São necessárias pelo menos 2 n / 10 etapas para encontrar uma tarefa satisfatória para uma fórmula n 10SAT variável aleatória" (sendo "aleatório", por exemplo, o modelo plantado de Achlioptas Coja-Oghlan , este é apenas um exemplo - não sei o que são números concretos razoáveis ​​de antemão).$P\neq NP$$2^{n/10}$

Tal conjectura pode resultar em uma previsão refutável de que qualquer sistema natural que tentará resolver isso falhará (por exemplo, ficará preso em um mínimo local), algo que você pode verificar com as experiências. Na verdade, não sou especialista nisso, mas, pelo que sei, como Joe Fitzsimons mencionou, essas previsões foram confirmadas com a computação adiabática. (Scott Aaronson também teve algumas experiências divertidas com bolhas de sabão.)

É claro que você também pode ver algumas "evidências empíricas" de no fato de as pessoas estarem tentando resolver problemas de otimização, criptoanalisar criptografias etc. e até agora não foram bem-sucedidas ...$P \neq NP$

O mundo real é um objeto de tamanho constante; portanto, não há como descartar um procedimento do mundo real em tempo polinomial para resolver problemas completos de NP que possuem uma constante enorme oculta na grande notação O.

De qualquer forma, além deste ponto, a suposição é uma afirmação da forma "não existe procedimento do mundo real que faça ..." Como alguém projeta um experimento para refutar tal afirmação? Se a suposição fosse algo como "Se fizermos X no mundo real, Y acontecer", isso poderá ser refutado com a execução de X. A afirmação de que queremos afirma a inexistência de algo, então não consigo ver um experimento decidir isso. Isso pode ser mostrado como uma conseqüência física das leis da física, mas isso é ainda mais difícil do que P vs NP, porque uma máquina de Turing segue as leis da física. Como não tivemos sucesso nem mesmo ao mostrar que as TMs não podem resolver problemas completos de NP em tempo polinomial, parece completamente inútil mostrar que nenhum processo físico pode resolver problemas completos de NP em tempo polinomial.

De fato, a versão física de P não é igual a NP, a saber, que nenhum sistema físico natural pode resolver o problema completo de NP é muito interessante. Existem algumas preocupações

1) O programa parece praticamente "ortogonal" à física experimental e teórica. Portanto, ele realmente não fornece (até agora) idéias úteis em física.

Existem alguns argumentos interessantes sobre como deduzir dessa versão física da conjectura algumas idéias da física, mas esses argumentos são razoavelmente "brandos" e têm brechas. (E é provável que esses argumentos sejam problemáticos, uma vez que se baseiam em conjecturas matemáticas muito difíceis, como NP não é igual a P e NP não é incluído no BQP que não entendemos.)

(Um comentário semelhante se aplica à "tese de orientação da Igreja".)

2) Embora o NP físico diferente de P seja uma conjectura mais ampla que o NP matemático diferente de P, também podemos considerá-lo mais restrito, pois os algoritmos que ocorrem na natureza (e mesmo os algoritmos criados pelo homem) parecem ser muito classe restrita de todos os algoritmos teoricamente possíveis. Será muito interessante entender formalmente essas restrições, mas, em qualquer caso, qualquer "prova" de esforço sugerida na pergunta será aplicada apenas a essas classes restritas.

3) Na modelagem científica, a complexidade computacional representa uma espécie de questão de segunda ordem, onde primeiro gostaríamos de modelar um fenômeno natural e ver o que pode ser previsto com base no modelo (deixando de lado a teoria da complexidade computacional). Dar muito peso aos problemas de complexidade computacional no estágio de modelagem não parece ser proveitoso. Em muitos casos, o modelo é computacionalmente intratável, mas ainda pode ser viável para problemas que ocorrem naturalmente ou útil para entender os fenômenos.

4) Concordo com Boaz que a questão assintótica não é necessária para "quebrar o negócio". Ainda é um assunto bastante sério quando se trata da relevância das questões de complexidade computacional para a modelagem da vida real.

Se você me permitir generalizar um pouquinho ... Vamos estender a pergunta e pedir outras suposições de dureza teóricas da complexidade e suas conseqüências para experimentos científicos. (Vou me concentrar na física.) Recentemente, houve um programa bem-sucedido para tentar entender o conjunto de correlações permitidas entre dois dispositivos de medição que, embora separados espacialmente, executam uma medição em um sistema físico (possivelmente não relacionado localmente) ( 1) Sob essa e outras configurações semelhantes, pode-se usar as suposições sobre a dureza da complexidade da comunicação para derivar limites estreitos que reproduzem as correlações permitidas para a mecânica quântica.

Para dar um sabor, deixe-me descrever um resultado anterior a esse respeito. Uma caixa Popescu-Rohrlich (ou caixa PR) é um dispositivo imaginário que reproduz correlações entre os dispositivos de medição que são consistentes com o princípio de que nenhuma informação pode viajar mais rápido que a luz (chamado princípio de não sinalização ).

S. Popescu & D. Rohrlich, Não-localidade quântica como axioma, Found. Phys. 24, 379-385 (1994).

Podemos ver isso como um exemplo de complexidade da comunicação que tem alguma influência. A idéia de que dois observadores devem se comunicar implicitamente pressupõe alguma restrição que um físico não chamaria de sinalização. Mudando essa idéia, que tipos de correlações são possíveis entre dois dispositivos de medição restritos por nenhuma sinalização? É isso que Popescu & Rohrlich estudam. Eles mostraram que esse conjunto de correlações permitidas é estritamente maior do que o permitido pela mecânica quântica, que por sua vez é estritamente maior do que o permitido pela física clássica.

A questão então se apresenta: o que torna o conjunto de correlações quânticas o conjunto "correto" de correlações, e não aquelas permitidas por nenhuma sinalização?

Para abordar essa questão, vamos supor que existem funções para as quais a complexidade da comunicação não é trivial. Meios apenas aqui não triviais que para calcular conjuntamente uma função booleana f (x, y), é preciso mais do que apenas um único bit (2). Surpreendentemente, mesmo essa suposição teórica de complexidade muito fraca é suficiente para restringir o espaço de correlações permitidas.

G. Brassard, H. Buhrman, N. Linden, AA Méthot, A. Tapp e F. Unger, Limite da não localidade em qualquer mundo em que a complexidade da comunicação não seja trivial, Phys. Rev. Lett. 96, 250401 (2006).

Observe que um resultado mais fraco já foi comprovado no doutorado. tese de Wim van Dam. O que Brassard et al. A prova é que o acesso às caixas de relações públicas, mesmo as que apresentam falhas e apenas produzem a correlação correta algumas vezes, permite banalizar completamente a complexidade da comunicação. Neste mundo, todas as funções booleanas de duas variáveis ​​podem ser computadas em conjunto transmitindo apenas um único bit. Isso parece um absurdo, então vamos analisar inversamente. Podemos tomar a não trivialidade da complexidade da comunicação como um axioma, e isso nos permite derivar o fato de que não observamos certas correlações mais fortes que o quantum em nossos experimentos.

Este programa que usa a complexidade da comunicação teve um sucesso surpreendentemente, talvez muito mais do que o correspondente para a complexidade computacional. Os papéis acima são realmente apenas a ponta do iceberg. Um bom lugar para começar a ler mais é esta revisão:

H. Buhrman, R. Cleve, S. Massar e R. de Wolf, Não-localidade e complexidade da comunicação, Rev. Mod. Phys. 82, 665-698 (2010).

ou uma pesquisa bibliográfica avançada dos outros dois artigos que citei.

Isso também levanta a questão interessante sobre por que a configuração de comunicação parece muito mais passível de análise do que a configuração de computação. Talvez isso possa ser o assunto de outra pergunta postada na história.

(1) Tomemos, por exemplo, os experimentos que medem algo conhecido como desigualdade de CHSH (um tipo de desigualdade de Bell ), onde o sistema físico consiste em dois fótons emaranhados e as medidas são medidas de polarização nos fótons individuais em dois locais espacialmente distantes.

(2) Esse bit único é necessário sempre que f (x, y) realmente depende de xey, pois o envio de zero bits não violaria a sinalização.

Além disso, existe alguma evidência numérica conhecida da matemática experimental a favor ou contra P ≠ N P$P \neq NP$

$NP \subseteq P/poly$

Agora, encontrar um circuito mínimo para SAT até o comprimento 10 é atualmente muito difícil. No entanto, algumas das idéias da teoria da complexidade geométrica permitem obter resultados semelhantes com uma pesquisa computacional mais eficiente (acho apenas exponencial em vez de duplamente exponencial). Uma das conjecturas de Mulmuley é que, de fato, essa pesquisa pode ser feita em tempo polinomial, mas ainda estamos longe de provar algo próximo disso.

As definições de "tempo polinomial" e "tempo exponencial" descrevem o comportamento limitante do tempo de execução conforme o tamanho da entrada cresce até o infinito. Por outro lado, qualquer experimento físico necessariamente considera apenas entradas de tamanho limitado. Portanto, não há absolutamente nenhuma maneira de determinar experimentalmente se um determinado algoritmo é executado em tempo polinomial, tempo exponencial ou outra coisa.

Ou em outras palavras: o que Robin disse.

Deixe-me começar dizendo que concordo completamente com Robin. No que diz respeito à dobragem de proteínas, há um pequeno problema. Como em todos esses sistemas, a dobragem de proteínas pode ficar presa nos mínimos locais, o que parece estar negligenciando. O problema mais geral é simplesmente encontrar o estado fundamental de alguns hamiltonianos. Na verdade, mesmo se considerarmos apenas rotações (ou seja, qubits), esse problema está completo para o QMA.

Os hamiltonianos naturais são um pouco mais suaves, no entanto, do que alguns dos artificiais usados ​​para provar a integridade da QMA (que tendem a não refletir as interações naturais), mas mesmo quando restringimos as interações naturais de dois corpos em sistemas simples, o resultado ainda é um NP problema incompleto. De fato, isso forma a base de uma abordagem tentada para resolver problemas de NP usando a computação quântica adiabática. Infelizmente, parece que essa abordagem não funcionará para problemas de NP completos, devido a um problema bastante técnico relacionado à estrutura do nível de energia. No entanto, isso leva a uma conseqüência interessante de problemas existentes no NP que não são eficientemente solucionáveis ​​por natureza (com o que quero dizer processos físicos). Isso significa que existem sistemas que não conseguem resfriar com eficiência. Isto é,

O estudo de situações do mundo real de uma perspectiva computacional é bastante difícil devido ao "salto" contínuo e discreto. Embora todos os eventos no mundo real (supostamente) sejam executados em tempo contínuo, os modelos que costumamos usar são implementados em tempo discreto. Portanto, é muito complicado definir quão pequeno ou grande deve ser um passo, qual deve ser o tamanho do problema etc.

Escrevi um resumo no artigo de Aaronson sobre o assunto, porém não está em inglês. Veja o documento original .

Pessoalmente, ouvi falar de outro exemplo de um problema do mundo real modelado em computação. O artigo trata de modelos de sistemas de controle baseados no agrupamento de aves. Embora demore um pouco na vida real para as aves, é intratável ("uma torre de 2s") quando analisado como um problema computacional. Veja o artigo de Bernard Chazelle para detalhes.

[Editar: Esclareceu a parte sobre o trabalho de Chazelle. Obrigado por fornecer informações precisas.]

Ainda voto pelo problema do corpo n como um exemplo de intratabilidade do PN. Os senhores que se referem às soluções numéricas esquecem que a solução numérica é um modelo recursivo, e não uma solução em princípio da mesma maneira que uma solução analítica. A solução analítica de Qui Dong Wang é intratável. As proteínas que podem dobrar e os planetas que podem orbitar em sistemas com mais de dois corpos são sistemas físicos, não soluções algorítmicas do tipo que o problema da P-NP aborda.

Devo também apreciar as dificuldades de chazisop com soluções em tempo contínuo. Se o tempo ou o espaço são contínuos, os espaços de estado em potencial se tornam incontáveis ​​(aleph one).

$n$