DAA - Classe P & NP

In Informatica, molti problemi vengono risolti laddove l'obiettivo è massimizzare o minimizzare alcuni valori, mentre in altri problemi si cerca di scoprire se esiste o meno una soluzione. Quindi, i problemi possono essere classificati come segue:

Problema di ottimizzazione

I problemi di ottimizzazione sono quelli per i quali l'obiettivo è massimizzare o minimizzare alcuni valori. Per esempio,

• Trovare il numero minimo di colori necessari per colorare un dato grafico.

• Trovare il percorso più breve tra due vertici in un grafo.

Problema decisionale

Esistono molti problemi per i quali la risposta è Sì o No. Questi tipi di problemi sono noti come decision problems. Per esempio,

• Se un dato grafico può essere colorato solo con 4 colori.

• Trovare il ciclo hamiltoniano in un grafo non è un problema decisionale, mentre controllare un grafo sia hamiltoniano o meno è un problema decisionale.

Cos'è la lingua?

Ogni problema decisionale può avere solo due risposte, sì o no. Quindi, un problema decisionale può appartenere a una lingua se fornisce una risposta "sì" per un input specifico. Una lingua è la totalità degli input per i quali la risposta è Sì. La maggior parte degli algoritmi discussi nei capitoli precedenti lo sonopolynomial time algorithms.

Per la dimensione di input n, se la complessità temporale nel caso peggiore di un algoritmo è O(n^k), dove k è una costante, l'algoritmo è un algoritmo temporale polinomiale.

Algoritmi come Matrix Chain Multiplication, Single Source Shortest Path, All Pair Shortest Path, Minimum Spanning Tree, ecc. Vengono eseguiti in tempo polinomiale. Tuttavia ci sono molti problemi, come il venditore ambulante, la colorazione ottimale del grafo, i cicli hamiltoniani, la ricerca del percorso più lungo in un grafo e il soddisfacimento di una formula booleana, per la quale non sono noti algoritmi temporali polinomiali. Questi problemi appartengono a un'interessante classe di problemi, denominataNP-Complete problemi, il cui stato è sconosciuto.

In questo contesto, possiamo classificare i problemi come segue:

Classe P.

La classe P è costituita da quei problemi che sono risolvibili in tempo polinomiale, cioè questi problemi possono essere risolti nel tempo O(n^k) nel peggiore dei casi, dove k è costante.

Questi problemi sono chiamati tractable, mentre altri vengono chiamati intractable or superpolynomial.

Formalmente, un algoritmo è un algoritmo temporale polinomiale, se esiste un polinomio p(n) in modo tale che l'algoritmo possa risolvere qualsiasi istanza di dimensione n in un tempo O(p(n)).

Problema che richiede Ω(n⁵⁰) il tempo per risolvere sono essenzialmente intrattabili per i grandi n. L'algoritmo del tempo polinomiale più noto viene eseguito nel tempoO(n^k) per un valore piuttosto basso di k.

Il vantaggio nel considerare la classe degli algoritmi tempo-polinomiali è che tutto ragionevole deterministic single processor model of computation possono essere simulati l'uno sull'altro con al massimo un polinomio slow-d

Classe NP

La classe NP è costituita da quei problemi verificabili in tempo polinomiale. NP è la classe di problemi decisionali per i quali è facile verificare la correttezza di una risposta asserita, con l'ausilio di poche informazioni extra. Quindi, non stiamo chiedendo un modo per trovare una soluzione, ma solo per verificare che una presunta soluzione sia davvero corretta.

Ogni problema in questa classe può essere risolto in tempo esponenziale utilizzando una ricerca esaustiva.

P contro NP

Ogni problema decisionale risolvibile da un algoritmo tempo polinomiale deterministico è risolvibile anche da un algoritmo tempo polinomiale non deterministico.

Tutti i problemi in P possono essere risolti con algoritmi di tempo polinomiale, mentre tutti i problemi in NP - P sono intrattabili.

Non è noto se P = NP. Tuttavia, molti problemi sono noti in NP con la proprietà che se appartengono a P, allora si può dimostrare che P = NP.

Se P ≠ NP, ci sono problemi in NP che non sono né in P né in NP-Complete.

Il problema appartiene alla classe Pse è facile trovare una soluzione al problema. Il problema appartiene aNP, se è facile controllare una soluzione che potrebbe essere stata molto noiosa da trovare.