Quali sono le differenze tra NP, NP-Completo e NP-Hard?

https://stackoverflow.com/questions/1857244

13-09-2019
|

Domanda

Quali sono le differenze tra NP, NP-Completo e NP-Hard?

Io sono a conoscenza di molte risorse in tutto il web.Mi piacerebbe leggere le vostre spiegazioni, e il motivo è che potrebbe essere diverso da quello che c'è fuori, o c'è qualcosa che io non sono a conoscenza di.

Soluzione

Presumo che stai cercando intuitiva definizioni, poiché le definizioni tecniche richiedono un bel po ' di tempo per capire.Prima di tutto, ricordiamoci che un preliminare necessario concetto per comprendere tali definizioni.

Problema della decisione:Un problema con un sì o no risposta.

Ora, cerchiamo di definire tali classi di complessità.

P

P è una complessità di classe che rappresenta l'insieme di tutti i problemi di decisione che può essere risolto in tempo polinomiale.

Che, data un'istanza del problema, la risposta sì o no, può essere deciso in tempo polinomiale.

Esempio

Dato un grafico collegato G, possono i suoi vertici essere colorato utilizzando due colori in modo che il bordo non è monocromatica?

Algoritmo:iniziare con un numero arbitrario di vertice, il colore è rosso e tutti i suoi vicini blu e continuare.Interrompere quando si esegue fuori di vertici o si è costretti a fare un bordo hanno entrambi gli endpoint essere dello stesso colore.

NP

NP è una complessità di classe che rappresenta l'insieme di tutti i problemi di decisione per la quale i casi in cui la risposta è "sì" sono prove che si possono verificare in tempo polinomiale.

Questo significa che se qualcuno ci dà un'istanza del problema e un certificato (a volte chiamato un testimone) per la risposta " sì, siamo in grado di verificare in tempo polinomiale.

Esempio

Integer fattorizzazione è in NP.Questo è il problema che ha dato i numeri interi n e m, c'è un intero f con 1 < f < m, in modo tale che f divide n (f è un piccolo fattore di n)?

Questo è un problema decisionale in quanto le risposte sono sì o no.Se qualcuno ci porge un'istanza del problema (in modo che la mano ci interi n e m) e un numero intero f con 1 < f < m, e pretendiamo che f è un fattore di n (il certificato), siamo in grado di controllare la risposta in tempo polinomiale eseguendo la divisione n / f.

NP-Completo

NP-Completo è di una complessità di classe che rappresenta l'insieme di tutti i problemi X in NP per i quali è possibile ridurre qualsiasi altro problema NP Y per X in tempo polinomiale.

Intuitivamente, questo significa che siamo in grado di risolvere Y rapidamente se sappiamo come risolvere X rapidamente.Appunto, Y è riducibile a X, se c'è un algoritmo in tempo polinomiale f per trasformare le istanze y di Y per le istanze x = f(y) di X in tempo polinomiale, con la proprietà che la risposta a y sì, se e solo se la risposta a f(y) è sì.

Esempio

3-SAT.Questo è il problema in cui ci viene data una congiunzione (And) di 3-clausola di alternative (ORs), dichiarazioni di forma

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

dove ogni x_vij è una variabile booleana o la negazione di una variabile da un numero finito elenco predefinito (x_1, x_2, ... x_n).

Si può dimostrare che ogni NP problema può essere ridotto a 3-SAT.La prova di ciò è tecnico e richiede l'utilizzo di tecniche di definizione di NP (basato sul non-deterministico macchine di Turing).Questo è noto come Cucinare con il teorema di.

Ciò che rende NP-completi problemi l'importante è che se deterministica in tempo polinomiale algoritmo può essere trovato per risolvere uno di loro, ogni NP problema è risolvibile in tempo polinomiale (un problema per domarli tutti).

NP-hard

Intuitivamente, questi sono i problemi che sono almeno così difficile come l'NP-completi problemi.Nota che NP-hard problemi non è necessario essere in NP, e essi non devono essere problemi di decisione.

La definizione precisa è qui che un problema X è NP-hard, se c'è NP-completa Y, in modo tale che Y è riducibile a X in tempo polinomiale.

Ma dal momento che qualsiasi NP-completo di problema può essere ridotto a qualsiasi altro NP-completi problema in tempo polinomiale, tutte NP-completi problemi possono essere ridotti a qualsiasi NP-hard problema in tempo polinomiale.Quindi, se c'è una soluzione a uno NP-hard problema in tempo polinomiale, c'è una soluzione a tutti i problemi NP in tempo polinomiale.

Esempio

Il problema della terminazione 'e NP-hard problema.Questo è il problema che, dato un programma P e ingresso I, sarà battuta d'arresto?Questo è un problema della decisione, ma non è in NP.È chiaro che qualsiasi NP-completo di problema può essere ridotto a questo.Come altro esempio, qualsiasi NP-completi problema è NP-hard.

Il mio preferito NP-completo è il problema Minesweeper problema.

P = NP

Questo è il più famoso problema in computer science, una delle più importanti questioni in sospeso nel campo delle scienze matematiche.Infatti, il Clay Institute sta offrendo un milione di dollari per una soluzione al problema (Stephen Cook writeup sull'Argilla sito web è molto buona).

È chiaro che P è un sottoinsieme di NP.La questione aperta è se o non NP problemi sono deterministica in tempo polinomiale soluzioni.Esso è in gran parte ritiene che essi non.Qui è un ottimo recente articolo su l'ultima (e l'importanza) del P = NP problema: Lo Stato del P versus NP problema.

Il miglior libro sull'argomento è Computer e Intractability da Garey e Johnson.

Altri suggerimenti

Ho cercato in giro e vedere molte spiegazioni lunghe. Ecco un piccolo grafico che può essere utile per riassumere:

Si noti come difficoltà aumenta cima a fondo: qualsiasi NP può essere ridotto a NP-completo , e qualsiasi NP-completo può essere ridotto a NP-Hard , il tutto in P (polinomiale) tempo.

Se si riesce a risolvere una classe più difficile del problema a tempo P, che significherà hai trovato come risolvere tutti i problemi più facile in tempo P (ad esempio, dimostrando P = NP, se a capire come risolvere qualsiasi NP problema completo in tempo P).

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Note sulle voci Yes o No:

* Un problema NP che è anche P è risolvibile in tempo P.
** un problema NP-hard che è anche NP-completo è verificabile in tempo P.
*** problemi NP-completi (ognuno dei quali formano un sottoinsieme di NP-hard) potrebbe essere. Il resto della NP non è difficile.

Ho trovato anche questo diagramma molto utile nel vedere come tutto questi tipi corrispondono l'uno all'altro (prestare maggiore attenzione alla metà sinistra del diagramma).

Questa è una risposta molto informale alla domanda posta.

Può 3233 essere scritto come il prodotto di altri due numeri più grandi di 1? C'è un modo di camminare un percorso intorno a tutte le Sette Ponti di Königsberg senza di prendere qualsiasi ponte due volte? Questi sono esempi di domande che condividono un tratto comune. Esso non può essere ovvio come determinare in modo efficiente la risposta, ma se la risposta è 'sì', allora c'è un breve e rapido per verificare la prova. Nel primo caso una fattorizzazione non banale di 51; nel secondo, un percorso per camminare i ponti (il montaggio dei vincoli).

Un problema di decisione è una raccolta di domande con sì o no risposte che variano solo in un parametro. Dicono che il problema COMPOSITE = { "Is composito n": n è un numero intero} o EULERPATH = { "fa il G grafico di avere un percorso di Eulero?": G è un grafo finito}.

Ora, alcuni problemi di decisione si prestano a efficiente, se non algoritmi evidenti. Eulero ha scoperto un algoritmo efficiente per problemi come le "Sette ponti di Königsberg" più di 250 anni fa.

D'altra parte, per molti problemi di decisione, non è ovvio come ottenere la risposta - ma se si conosce qualche pezzo aggiuntivo di informazioni, è ovvio come fare per provare che hai la risposta giusta. COMPOSITE è come questo: la divisione di prova è l'algoritmo ovvio, ed è lento: per fattorizzare un numero di 10 cifre, è necessario provare qualcosa di simile 100.000 possibili divisori. Ma se, per esempio, qualcuno vi ha detto che il 61 è un divisore di 3233, semplice divisione lungo è un modo efficace per vedere che siano corrette.

La classe di complessità NP è la classe di problemi decisionali in cui le risposte 'sì' hanno poco a stato, rapido per verificare le prove. Come COMPOSITE. Un punto importante è che questa definizione non dice nulla su quanto sia difficile il problema è. Se si dispone di un modo efficiente corretto per risolvere un problema decisionale, basta scrivere i passaggi della soluzione è una prova sufficiente.

ricerca Algoritmi continua, e nuovi algoritmi intelligenti vengono create per tutto il tempo. Un problema che potrebbe non sapere come risolvere in modo efficiente oggi potrebbe rivelarsi avere un efficiente (se non ovvio) soluzione di domani. In realtà, ci sono voluti i ricercatori fino 2002 di trovare una soluzione efficace per COMPOSITE! Con tutti questi progressi, si ha davvero da chiedersi: È questo po 'di avere prove brevi solo un'illusione? Forse tutti problema di decisione che si presta a prove efficienti è una soluzione efficiente? Nessuno sa .

Forse il più grande contributo a questo campo è venuto con la scoperta di una classe particolare di problemi NP. Giocando con modelli circuitali per il calcolo, Stephen Cook ha trovato un problema decisionale della varietà NP che era dimostrabilmente come duro o più difficile di tutti altro problema NP. Una soluzione efficiente per la soddisfacibilità booleana potrebbe essere utilizzato per creare un efficiente soluzione per qualsiasi altro problema in NP. Poco dopo, Richard Karp ha dimostrato che un certo numero di altri problemi di decisione potrebbe servire allo stesso scopo. Questi problemi, in un certo senso i "più duri" problemi in NP, divenne noto come NP-completi problemi.

Naturalmente, NP è solo una classe di problemi decisionali. Molti problemi non sono naturalmente espressi in questo modo: "trovare i fattori di N", "trovare il percorso più breve nel grafo G che visita ogni vertice", "dare una serie di assegnazioni di variabili che rende la seguente espressione booleana vero". Anche se si può informalmente talk su alcuni di questi problemi che sono "in NP", tecnicamente che non ha molto senso - non sono problemi di decisione. Alcuni di questi problemi potrebbe anche avere lo stesso tipo di potere come un problema NP-completo: una soluzione efficace a questi problemi (non-decision) porterebbe direttamente ad una soluzione efficace a qualsiasi problema NP. Un problema come questo si chiama NP-hard .

In aggiunta alle altre grandi risposte, qui è la la gente usa per mostrare la differenza tra NP, NP-completi e NP-hard:

entrare descrizione dell'immagine qui

P (polinomio Time): Come nome stesso suggerisce, questi sono i problemi che possono essere risolti in tempo polinomiale

NP (Time non deterministico polinomiale): Questi sono i problemi decisionali che possono essere verificate in tempo polinomiale. Ciò significa che, se io affermo che c'è una soluzione tempo polinomiale per un particolare problema, mi chiedi di dimostrarlo. Poi, io vi darò una prova che si può facilmente verificare in tempo polinomiale. Questo tipo di problemi sono chiamati problemi NP. Si noti che, qui non stiamo parlando di se c'è una soluzione tempo polinomiale per questo problema o meno. Ma stiamo parlando di verificare la soluzione di un dato problema in tempo polinomiale.

NP-Hard: Queste sono almeno altrettanto duro come i problemi più duri in NP. Se siamo in grado di risolvere questi problemi in tempo polinomiale, siamo in grado di risolvere qualsiasi problema NP che possa esistere. Si noti che questi problemi non sono necessariamente problemi NP. Questo significa che ci può / non-verificare la soluzione a questi problemi in tempo polinomiale.

NP-completo: Questi sono i problemi che sono sia NP e NP-Hard. Ciò significa che, se possiamo risolvere questi problemi, possiamo risolvere qualsiasi altro problema NP e le soluzioni a questi problemi può essere verificata in tempo polinomiale.

Il modo più semplice per spiegare P v. NP e quali senza entrare in tecnicismi è quello di confrontare "problemi di parola" con "molteplici problemi choice".

Quando si sta tentando di risolvere un "problema parola" bisogna trovare la soluzione da zero. Quando si sta cercando di risolvere un "problemi a scelta multipla" avete una scelta: o risolverlo come se fosse un "problema parola", o cercare di inserire in ciascuna delle risposte date a te, e scegliere la risposta candidato che si adatta.

Spesso accade che un "problema a scelta multipla" è molto più facile che il corrispondente "problema parola":. Sostituendo le risposte candidati e verificare se si inseriscono può richiedere molto meno sforzo che trovare la risposta giusta da zero

Ora, se siamo d'accordo lo sforzo che richiede tempo polinomiale "facile" allora la classe P consisterebbe di "semplici problemi di parola", e la classe NP consisterebbe di "facili molteplici problemi choice".

L'essenza di P v NP è la domanda: "Ci sono dei semplici problemi a risposta multipla che non sono facili come problemi di parola"? Cioè, ci sono problemi per i quali è facile verificare la validità di una data risposta, ma trovare quella risposta da zero è difficile?

Ora che abbiamo capito intuitivamente ciò che NP è, dobbiamo sfidare la nostra intuizione. Si scopre che ci sono "problemi a risposta multipla", che, in un certo senso, sono più duro di tutti: se si potrebbe trovare una soluzione a una di quelle "più duri di tutti loro" problemi si potrebbe essere in grado di trovare una soluzione a tutti problemi NP! Quando Cook scoprì questo 40 anni fa è venuto come una sorpresa completa. Questi "più duri di loro tutti i" problemi sono noti come NP-hard. Se si trova una "soluzione del problema parola" a uno di loro si dovrebbe trovare automaticamente una "soluzione word problema" per ogni "facile problema di scelta multipla"!

Infine, problemi NP-completi sono quelli che sono allo stesso tempo NP e NP-hard. A seguito della nostra analogia, sono allo stesso tempo "facile come problemi a risposta multipla" e "il più duro di tutti come problemi di parola".

Credo che possiamo rispondere molto più succintamente. Ho risposto una domanda relativa , e la copia la mia risposta da lì

Ma in primo luogo, un problema NP-hard è un problema per il quale non possiamo dimostrare che esiste una soluzione tempo polinomiale. NP-difficile di qualche "problema-P" di solito è provata da conversione di un già dimostrato problema NP-hard al "problema-P" in tempo polinomiale.

Per rispondere al resto della domanda, è necessario prima capire quali problemi NP-hard sono anche NP-completo. Se un problema NP-hard appartiene all'insieme NP, allora è NP-completo. Appartenere a impostare NP, un problema deve essere

(i) un problema decisionale,
  (Ii) il numero di soluzioni al problema dovrebbe essere finito e ogni soluzione deve essere di lunghezza polinomiale, e vendere   (Iii) dato una soluzione di lunghezza polinomiale, dovremmo essere in grado di dire se la risposta al problema è sì / no

Ora, è facile vedere che ci potrebbero essere molti problemi NP-hard che non appartengono a impostare NP e sono più difficili da risolvere. Per fare un esempio intuitivo, l'ottimizzazione-versione di commesso viaggiatore, dove abbiamo bisogno di trovare un programma di reale è più difficile di quanto la decisione-versione di commesso viaggiatore, dove abbiamo solo bisogno di determinare se un programma di lunghezza <= k esiste o no.

problemi NP-completi sono quei problemi che sono sia NP-Hard e nella classe di complessità NP. Pertanto, per dimostrare che un determinato problema è NP-completo, è necessario dimostrare che il problema è sia in NP e che è NP-hard.

I problemi che sono classe di complessità NP possono essere risolti non deterministico in tempo polinomiale e una possibile soluzione (cioè una dichiarazione) per un problema in NP possono essere verificati correttezza in tempo polinomiale.

Un esempio di una soluzione non deterministica al problema k-cricca sarebbe qualcosa di simile:

1) in modo casuale selezionare k nodi da un grafico

2) verificare che questi nodi k formano una cricca.

La strategia sopra è polinomiale nella dimensione del grafo di input e quindi il problema k-cricca è in NP.

Si noti che tutti i problemi deterministicamente risolvibili in tempo polinomiale sono anche in NP.

dimostrando che un problema è NP-hard in genere comporta una riduzione dal qualche altro problema NP-hard al vostro problema utilizzando una mappatura tempo polinomiale: http://en.wikipedia.org/wiki/Reduction_ (complessità)

Ci sono veramente bello risposte per questa particolare questione, quindi non c'è nessun punto di scrivere la mia spiegazione. Quindi cercherò di contribuire con una risorsa eccellente su diverse classi di complessità computazionale.

Per qualcuno che pensa che la complessità computazionale è solo circa P e NP, qui è la risorsa più esaustivo sui diversi problemi di complessità computazionale . Oltre ai problemi posti dalla OP, ha elencato circa 500 diverse classi di problemi di calcolo con le descrizioni bello e anche l'elenco degli articoli di ricerca fondamentali che descrivono la classe.

A quanto mi risulta, un NP-difficile problema non è "difficile" che un NP-completo problema. Infatti, per definizione, ogni problema NP-completo è:

in NP
NP-difficile

- Intro. agli algoritmi (3ed) da Cormen, Leiserson, Rivest e Stein, pg 1069

Trovare qualche defintion interessante:

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow