Cosa sarebbe un P = NP prova di essere come, ipoteticamente?

Question

sarebbe un algoritmo di tempo polinomiale ad uno specifico problema NP-completo, o solo ragionamenti astratti che dimostrano soluzioni ai problemi NP-completi esistono?

Sembra che il un algoithm specifico è molto più utile. Con esso, tutto quello che dovrete fare per risolvere un problema NP polinomialmente è quello di convertirlo in specifico problema NP-completo per i quali la prova ha una soluzione, e abbiamo finito.

Answer 1

P = NP: "La 3SAT problema è un classico problema NP completo In questa dimostrazione. , dimostriamo un algoritmo per risolverlo che ha un asintotica rilegato di (n ^ 99 log log n). per prima cosa ... "

P = NP: ". Si supponga c'era un algoritmo polinomiale per il 3SAT problema Questo implicherebbe che .... che per ..... implica che possiamo fare .... e poi ... e poi ... il che è impossibile. Questo era tutto predicata su un algoritmo di tempo polinomiale per 3SAT. Così P ! = NP. "

Aggiorna : Forse qualcosa di simile questo documento (per P! = NP).

UPDATE 2 : Ecco un video di Michael Sipser delineare una prova per P! = NP

Answer 2

Chiamatemi pessimista, ma sarà così:

...

∴, P ≠ NP

QED

Answer 3

Ci sono alcuni meta-risultati su ciò che un P = NP o P ≠ NP prova può non simile. I dettagli sono abbastanza tecnico, ma è noto che la prova non può essere

• relativizzazione , che tipo di significa che la prova deve utilizzare l'esatta definizione di macchina di Turing usata, perché con alcune modifiche ( "oracoli", come molto potenti istruzioni CISC aggiunti al set di istruzioni) P = NP, e con alcune altre modifiche, P ≠ NP. Vedi anche questo post del blog per una bella spiegazione di relativizzazione.

• naturale , una proprietà di diversi classici circuito noreferrer"> algebrizing , una generalizzazione di relativizzazione.

Answer 4

Si potrebbe assumere la forma di dimostrare che assumendo P ≠ NP porta ad una contraddizione.

Answer 5

Non potrebbe essere collegata al P e NP in modo semplice ... molti teoremi ora si basano su P! = NP, così dimostrando un assunto fatto di essere falso sarebbe fare una grande differenza. Anche dimostrando qualcosa come costante il rapporto approssimazione per TS dovrebbe essere abbastanza IIRC. Credo che, l'esistenza di NPI (GI) e altri set si basa anche su P! = NP, così facendo qualcuno di loro pari a P o NP potrebbe cambiare completamente la situazione.

IMHO tutto accade ora su un livello molto astratto. Se qualcuno dimostra nulla P = /! = NP, non deve parlare di uno di questi gruppi o anche un problema specifico.

Answer 6

Probabilmente sarebbe nella forma di una riduzione da un problema NP ad un problema P. Vedere la pagina Wikipedia su .

o

Ti piace questa prova proposto da Vinay Deolalikar .

Answer 7

Set N uguale alla identità moltiplicativa. Poi NP = P. QED. ; -)

Answer 8

Il modo più semplice è quello di dimostrare che c'è una soluzione tempo polinomiale ai problemi della classe NP-completo. Questi sono problemi che sono in NP e sono reducable ad uno dei noti problema np. Questo significa che si potrebbe dare un algoritmo più veloce per dimostrare le href="http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047" problema originale posto da Stephen Cook o molti altri che hanno dimostrato anche di essere NP-completo. Vedi seminale carta e questo libro per i problemi più interessanti. E 'stato dimostrato che se a risolvere uno di questi problemi l'intera classe di complessità crolla. edit: Devo aggiungere che stavo parlando con un mio amico che sta studiando il calcolo quantistico. Anche se non avevo idea di cosa vuol dire, ha detto che una prova certa / esperimento? nel mondo quantistico potrebbe rendere l'intera classe di complessità, voglio dire tutto, discutibile. Se qualcuno qui sa di più su questo, si prega di rispondere.

Ci sono stati anche numerosi tentativi al problema senza dare un algoritmo formale. Si potrebbe provare a contare il set. Theres la prova di Robert / Seymore. La gente ha anche cercato di risolverlo utilizzando la prova diagonlization collaudato (utilizzato anche per dimostrare che ci sono problemi che non si può mai risolvere). Razborov ha anche mostrato che se ci sono alcune funzioni unidirezionali allora ogni prova non può dare una risoluzione. Ciò significa che le nuove tecniche saranno necessari al fine di risolvere questo problema.

Il suo stato 38 anni da quando il lavoro originale è stato pubblicato e non v'è ancora alcun segno di una prova. Non solo, ma molti problemi che i matematici erano stati in posa prima della nozione di classi di complessità è arrivato ha dimostrato di essere NP. Perciò molti matematici e informatici ritengono che alcuni dei problemi sono così fondamentali che un nuovo tipo di matematica può essere necessaria per risolvere il problema. Bisogna tenere a mente che le migliori menti razza umana ha da offrire hanno affrontato questo problema senza alcun successo. Penso che dovrebbe essere almeno decenni prima che qualcuno le crepe del puzzle. Ma anche se c'è una soluzione tempo polinomiale le costanti o l'esponente potrebbe essere così grande che sarebbe inutile nei nostri problemi.

C'è un eccellente sondaggio disponibile che dovrebbe rispondere alla maggior parte delle vostre domande: http: // www .scottaaronson.com / documenti / pnp.pdf .

Answer 9

Di certo una prova descrittiva è la più utile, ma ci sono altre categorie di prove: è possibile, ad esempio, per fornire 'prove esistenza' che dimostrano che si tratta di possibile per trovare una risposta senza trovare (o, a volte, anche suggerendo come trovare) quella risposta.

Answer 10

Si sarebbe probabilmente guardare quasi esattamente come uno di questi

Answer 11

Buona domanda; si potrebbe prendere entrambe le forme. Ovviamente, l'algoritmo specifico sarebbe più utile, sì, ma non c'è la determinazione che questo sarebbe il modo in cui un P = NP teorica prova si sarebbe verificato. Dato che la natura dei problemi NP-completi e come comuni sono, sembrerebbe che più sforzo è stato messo in soluzione di questi problemi che è stato messo in soluzione del lato teorico ragionamento della equazione, ma questo è solo supposizione.

Answer 12

Ogni prova nonconstructive che P = NP in realtà non è. E 'implicherebbe che il seguente algoritmo esplicito 3-SAT viene eseguito in tempo polinomiale:

  

enumerare tutti i programmi. Sulla rotonda i , eseguire tutti i programmi numerati   meno di i per un passo. Se   un programma termina con un    soddisfazione di ingresso alla formula , ritorno true . Se un programma   termina con un prova formale che   non esiste un tale ingresso , il ritorno    false .

Se P = NP, allora esiste un programma che viene eseguito in O (poli (N)) ed emette un ingresso soddisfacente per la formula, se tale formula esiste.

Se P = CONP, esiste un programma che viene eseguito in O (poli (N)) e fornisce in uscita una prova formale che esiste nessuna formula, se esiste alcuna formula.

Se P = NP, quindi dal momento che P è chiusa sotto complemento NP = CONP. Quindi, esiste un programma che viene eseguito in O (poli (N)) e fa entrambe le cose. Questo programma è il k 'programma ° nella enumerazione. k è O (1) ! Dal momento che viene eseguito in O (poli (N)) nostra simulazione forza bruta richiede solo

  

k * O (poli (N)) + O (poli (N)) ^ 2

completa il quadro una volta che raggiunge il programma in questione. Come tale, la simulazione forza bruta viene eseguito in tempo polinomiale!

(Si noti che k è esponenziale nella dimensione del programma, questo approccio non è realmente fattibile, ma suggerisce che sarebbe difficile fare una prova nonconstructive che P = NP, anche se fosse il caso.)

Answer 13

In una certa misura, la forma di una tale prova deve avere dipende dal vostro punto di vista filosofico (= gli assiomi si ritengono per essere vero) - ad esempio, come un contructivist si dovrebbe chiedere la costruzione di un algoritmo reale che richiede tempo polinomiale per risolvere un problema NP-completo. Questo potrebbe essere fatto utilizzando la riduzione, ma non con una prova indiretta. In ogni caso, sembra davvero di essere molto improbabile:)

Answer 14

La prova sarebbe dedurre una contraddizione dal al presupposto che almeno un elemento (problema) di NP non è anche un elemento di P.

Answer 15

una lettura interessante che è in qualche modo relative a questo