Spiegare la dimostrazione per Vinay Deolalikar che P! = NP [chiusa]

Question

Recentemente c'è stato un carta galleggiando da Vinay Deolalikar in HP Labs che sostiene di avere dimostrato che P! = NP .

Qualcuno potrebbe spiegare come funziona questa prova per noi meno inclini matematicamente persone?

Answer 1

ho scansionato solo attraverso la carta, ma ecco una sintesi approssimativa di come tutti si blocca insieme.

Da pagina 86 del documento.

  

... tempo polinomiale   algoritmi riescono in successione   “Rompere” il problema in   piccoli sottoproblemi aggiunti a   l'altro attraverso condizionale   indipendenza. Di conseguenza, polinomio   algoritmi di tempo non possono risolvere   problemi nei regimi in cui blocchi il cui   ordine è lo stesso del sottostante   esempio problema richiede simultanea   risoluzione.

Altre parti dello spettacolo carta che certi problemi NP non può essere suddiviso in questo modo. Così NP / P =

La maggior parte del documento viene speso definire l'indipendenza condizionale e dimostrando questi due punti.

Answer 2

Dick Lipton ha una bella blog sulla carta e le sue prime impressioni di esso. Purtroppo, è anche tecnica. Da quello che posso capire, l'innovazione principale del Deolalikar sembra essere quella di utilizzare alcuni concetti dalla fisica statistica e teoria dei modelli finiti e legarli al problema.

Sono con Rex M con questo, alcuni risultati, per lo più quelli matematici non possono essere espresse per le persone che non hanno la padronanza tecnica.

Answer 3

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

  

I suoi argomenti ruota intorno a un compito particolare, il soddisfacibilità booleana, che chiede se un insieme di istruzioni logiche possono essere tutti contemporaneamente vere o se si contraddicono a vicenda. Questo è noto per essere un problema NP.

     

Deolalikar sostiene di aver dimostrato che   non esiste un programma che può completare   rapidamente da zero, e che   non è quindi un problema P. Il suo   argomento implica l'uso ingegnoso   fisica statistica, come egli utilizza un   struttura matematica che segue   molte delle stesse regole come una casuale   sistema fisico.

Gli effetti della sopra può essere molto significativo:

  

Se il risultato attuale, proverebbe   che le due classi P e NP non sono   identici, e imporre limiti severi   ciò che i computer possono compiere -   il che implica che molti compiti possono essere   fondamentalmente, irriducibilmente complesso.

     

Per alcuni problemi - tra cui   fattorizzazione - il risultato non lo fa   dicono chiaramente se essi possano essere risolti   velocemente. Ma un enorme sottoclasse di   problemi chiamato "NP-completo" sarebbe   condannato. Un esempio famoso è il   problema del commesso viaggiatore - trovare   il percorso più breve tra un insieme di   città. Tali problemi possono essere controllati   in fretta, ma se P ≠ NP allora non c'è   nessun programma per computer in grado di completare   rapidamente da zero.

Answer 4

Questa è la mia comprensione della tecnica prove: usa la logica del primo ordine di caratterizzare tutti gli algoritmi in tempo polinomiale, e poi spettacoli che per i grandi problemi SAT con determinate proprietà che nessun algoritmo tempo polinomiale può determinare la loro soddisfacibilità.

Answer 5

Un altro modo di pensare a questo proposito, che può essere del tutto sbagliato, ma è la mia prima impressione come io sto leggendo al primo passaggio, è che noi pensiamo di assegnare / compensazione termini di soddisfazione del circuito come la formazione e la rottura cluster di 'ordinato struttura', e che sta quindi utilizzando fisica statistici per dimostrare che non c'è abbastanza velocità nelle operazioni polinomiali di effettuare tali operazioni in un particolare "spazio delle fasi" delle operazioni, perché questi "cluster" finiscono per essere troppo a parte.

Answer 6

La prova dovrebbe coprire tutte le classi di algoritmi, come continua ottimizzazione globale .

Ad esempio, nel problema 3-SAT Dobbiamo valutare le variabili per soddisfare tutte le alternative di triple di queste variabili o le loro negazioni. Sguardo che x OR y può essere cambiato in ottimizzazione

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

e termini analogamente sette per alternative di tre variabili.

Trovare il minimo globale di una somma di tali polinomi per tutti i termini sarebbe risolvere il nostro problema. ( fonte )

E 'intenzione di tecniche standard combinatorie ai metodi using_gradient mondo continui, minimi locali rimozione metodi, algoritmi evolutivi. E 'completamente diverso regno - analisi numerica - non credo tale prova potrebbe davvero copertura

(?)

Answer 7

vale la pena di notare che con prove, "il diavolo è nei dettagli". La panoramica di alto livello è ovviamente qualcosa di simile:

  

Alcuni qualche tipo di relazione   tra gli elementi, dimostrare che questo   rapporto implica X e che   implica Y e quindi la mia tesi è   mostrato.

Voglio dire, può essere via induzione o qualunque altra forma di provare le cose, ma quello che sto dicendo è il livello elevato panoramica è inutile. Non v'è alcun punto di spiegarla. Anche se la domanda stessa si riferisce alla scienza informatica, è meglio lasciare ai matematici (pensiero è certamente incredibilmente interessante).