Classi NP Hard e NP-Complete

Un problema è nella classe NPC se è in NP ed è come hardcome qualsiasi problema in NP. Un problema èNP-hard se tutti i problemi in NP sono riducibili in tempo polinomiale ad esso, anche se potrebbe non essere in NP stesso.

Se esiste un algoritmo temporale polinomiale per uno di questi problemi, tutti i problemi in NP sarebbero risolvibili in tempo polinomiale. Questi problemi sono chiamatiNP-complete. Il fenomeno della NP-completezza è importante sia per ragioni teoriche che pratiche.

Definizione di NP-completezza

Una lingua B è NP-complete se soddisfa due condizioni

B è in NP
Ogni A in NP è il tempo polinomiale riducibile a B.

Se una lingua soddisfa la seconda proprietà, ma non necessariamente la prima, la lingua B è conosciuto come NP-Hard. Informalmente, un problema di ricercaB è NP-Hard se ce ne sono alcuni NP-Complete problema A che Turing riduce a B.

Il problema in NP-Hard non può essere risolto in tempo polinomiale, fino a quando P = NP. Se si dimostra che un problema è un NPC, non è necessario perdere tempo a cercare un algoritmo efficiente. Invece, possiamo concentrarci sull'algoritmo di approssimazione del progetto.

Problemi NP-Complete

Di seguito sono riportati alcuni problemi NP-Complete, per i quali non è noto alcun algoritmo temporale polinomiale.

Determinare se un grafico ha un ciclo hamiltoniano
Determinare se una formula booleana è soddisfacente, ecc.

Problemi NP-Hard

I seguenti problemi sono NP-Hard

Il problema della soddisfacibilità dei circuiti
Imposta copertina
Vertex Cover
Problema del commesso viaggiatore

In questo contesto, ora discuteremo che TSP è NP-Complete

TSP è NP-Complete

Il problema del venditore ambulante consiste in un venditore e un insieme di città. Il venditore deve visitare ciascuna delle città partendo da una certa e tornando nella stessa città. La sfida del problema è che il venditore ambulante vuole ridurre al minimo la durata totale del viaggio

Prova

Provare TSP is NP-Complete, prima dobbiamo dimostrarlo TSP belongs to NP. In TSP, troviamo un tour e controlliamo che il tour contenga ogni vertice una volta. Quindi viene calcolato il costo totale dei bordi del tour. Infine, controlliamo se il costo è minimo. Questo può essere completato in tempo polinomiale. CosìTSP belongs to NP.

In secondo luogo, dobbiamo dimostrarlo TSP is NP-hard. Per dimostrarlo, un modo è dimostrarloHamiltonian cycle ≤_p TSP (come sappiamo che il problema del ciclo hamiltoniano è NPcompleto).

Assumere G = (V, E) essere un'istanza del ciclo hamiltoniano.

Quindi, viene costruita un'istanza di TSP. Creiamo il grafico completoG^' = (V, E^'), dove

$$ E ^ {'} = \ lbrace (i, j) \ due punti i, j \ in V \: \: e \: i \ neq j $$

Pertanto, la funzione di costo è definita come segue:

$$ t (i, j) = \ begin {cases} 0 & if \: (i, j) \: \ in E \\ 1 & altrimenti \ end {cases} $$

Supponiamo ora che sia un ciclo hamiltoniano h esiste in G. È chiaro che il costo di ogni bordo inh è 0 in G^' come ogni bordo appartiene E. Perciò,h ha un costo di 0 in G^'. Quindi, if graphG ha un ciclo hamiltoniano, quindi un grafico G^' ha un tour di 0 costo.

Al contrario, lo assumiamo G^' ha un tour h^' di costo al massimo 0. Il costo dei bordi inE^' siamo 0 e 1per definizione. Quindi, ogni bordo deve avere un costo di0 come il costo di h^' è 0. Concludiamo quindi quelloh^' contiene solo bordi in E.

Lo abbiamo quindi dimostrato G ha un ciclo hamiltoniano, se e solo se G^' ha un giro di costo al massimo 0. TSP è NP-completo.