Explique a prova por Vinay Deolalikar que P != NP [fechado]

Question

Recentemente, tem havido um papel flutuando por Vinay Deolalikar no HP Labs, que afirma ter provado que P != NP.

Alguém poderia explicar como isso prova funciona para nós menos matematicamente decidido pessoas?

Answer 1

Eu só digitalizei o papel, mas aqui está um resumo aproximado de como tudo fica junto.

Da página 86 do papel.

... Os algoritmos de tempo polinomial são bem -sucedidos sucessivamente "quebrando" o problema em subproblemas menores que se uniram através da independência condicional. Consequentemente, os algoritmos de tempo polinomial não podem resolver problemas em regimes em que blocos cuja ordem é a mesma que a instância do problema subjacente requer resolução simultânea.

Outras partes do artigo mostram que certos problemas de NP não podem ser divididos dessa maneira. Assim np/= p

Grande parte do artigo é gasto definindo a independência condicional e provando esses dois pontos.

Answer 2

Dick Lipton tem um bom entrada no blog sobre o jornal e suas primeiras impressões disso. Infelizmente, também é técnico. Pelo que posso entender, a principal inovação de Deolalikar parece ser usar alguns conceitos da física estatística e da teoria dos modelos finitos e vinculá -los ao problema.

Estou com o Rex M com este, alguns resultados, principalmente os matemáticos, não podem ser expressos às pessoas que não têm domínio técnico.

Answer 3

Eu gostei disso ( http://www.newscientist.com/article/dn19287-p--np-its-bad-news-for-the-power-of-computing.html ):

Seu argumento gira em torno de uma tarefa específica, o problema da satisfação booleana, que pergunta se uma coleção de declarações lógicas pode ser simultaneamente verdadeira ou se elas se contradizem. Sabe -se que isso é um problema de NP.

Deolalikar afirma ter mostrado que não há um programa que possa concluí -lo rapidamente do zero e que, portanto, não é um problema de P. Seu argumento envolve o uso engenhoso da física estatística, pois ele usa uma estrutura matemática que segue muitas das mesmas regras que um sistema físico aleatório.

Os efeitos do exposto acima podem ser bastante significativos:

Se o resultado permanecer, provaria que as duas classes P e NP não são idênticas e impõem limites graves ao que os computadores podem realizar - o que implica que muitas tarefas podem ser fundamentalmente, irredutivelmente complexas.

Para alguns problemas - incluindo fatorização - o resultado não diz claramente se eles podem ser resolvidos rapidamente. Mas um enorme subclasse de problemas chamados "NP-complete" seria condenado. Um exemplo famoso é o problema do vendedor ambulante - encontrando a rota mais curta entre um conjunto de cidades. Esses problemas podem ser verificados rapidamente, mas se p ≠ np, não houver um programa de computador que possa completá -los rapidamente do zero.

Answer 4

Esse é o meu entendimento da técnica de prova: ele usa a lógica de primeira ordem para caracterizar todos os algoritmos de tempo polinomial e, em seguida, mostra que, para grandes problemas de SAT, com certas propriedades, nenhum algoritmo de tempo polinomial pode determinar sua satisfação.

Answer 5

Uma outra maneira de pensar sobre isso, que pode estar totalmente errada, mas é minha primeira impressão, pois estou lendo no primeiro passe, é que pensamos em atribuir/limpar termos na satisfação do circuito como formação e quebra de aglomerados de 'ordenados estrutura ', e que ele está usando a física estatística para mostrar que não há velocidade suficiente nas operações polinomiais para executar essas operações em um "espaço de fase" de operações específico, porque esses "clusters" acabam sendo muito distantes.

Answer 6

Tal prova teria de cobrir todas as classes de algoritmos, como contínua otimização global.

Por exemplo, no 3-SAT problema temos de avaliar as variáveis para cumprir todas as alternativas de triplos destas variáveis ou os seus opostos.Olhar que x OR y podem ser alteradas para otimizar

((x-1)^2+y^2)((x-1)^2+(y-1)^2)(x^2+(y-1)^2)

e de modo análogo sete termos de alternativas de três variáveis.

Encontrar o mínimo global de uma soma de tais polinômios, para todos os termos resolveria o nosso problema.(origem)

Ele vai fora de padrão combinatória técnicas para a contínua mundo using_gradient métodos, local minims remoção de métodos, algoritmos evolutivos.É completamente diferente reino - análise numérica - eu não acredito que a prova poderia realmente capa (?)

Answer 7

Vale a pena notar que, com provas, "o diabo está nos detalhes". A visão geral de alto nível é obviamente algo como:

Alguns tipo de relação entre os itens mostram que esse relacionamento implica x e isso implica y e, portanto, meu argumento é mostrado.

Quero dizer, pode ser via Indução Ou qualquer outra forma de provar coisas, mas o que estou dizendo é que a visão geral de alto nível é inútil. Não faz sentido explicar isso. Embora a questão em si esteja relacionada à ciência da computação, é melhor deixar os matemáticos (achou certamente incrivelmente interessante).