Calcolabilità e Complessità : classi di complessità

Cominciamo, per rompere il ghiaccio, con la prima domanda che quest'anno ha fatto all'orale, o almeno a tutti quelli a cui ho assistito io, compreso il mio.
La domanda era la seguente: "Che vuol dire che un problema appartiene a NP-COMPLETE?".
Innanzitutto facciamo un ripasso sulle classi di complessità.

Diciamo P={L|DTM M con L=L(M) && Tm=O(n^k), k costante}. In altre parole, alla classe P (polynomial time) appartengono tutti i problemi risolvibili con una macchina di Turing deterministica (DTM) in tempo polinomiale (Tm=O(n^k), k costante).
Diciamo NP={L|NTM M con L=L(M) && Tm=O(n^k), k costante}. In altre parole, alla classe NP (non-deterministic polynomial time) appartengono tutti i problemi risolvibili con una macchina di Turing non deterministica (NTM) in tempo polinomiale (Tm=O(n^k), k costante).

P è sottinsieme di NP, e entrambe le classi sono sottinsieme di PSPACE (classe di linguaggi risolvibili in spazio polinomiale) che, a sua volta, è sottinsieme di EXPTIME (DTM che lavorano in tempo esponenziale).
Per dire che un problema appartiene a NP ma non a P, useremo una sottoclasse detta NP-COMPLETE, in cui ci sono problemi almeno difficili quanto quelli in NP.
Se un linguaggio L appartenesse a NP-COMPLETE e, al tempo stesso, appartenesse a P, allora P=NP. Ma per fortuna questa cosa non è verificata, quindi c'è una dimostrazione in meno da fare.

Ora torniamo alla domanda di partenza: "Che vuol dire che un problema appartiene a NP-COMPLETE?".
Un problema, o linguaggio, L appartiene a NP-COMPLETE se si verificano due condizioni:
1. l'appartenenza di L a NP;
2. l'appartenenza di L a NP-HARD.

Ora è uscita fuori una nuova classe di complessità, NP-HARD. Niente paura, ora vediamo che è.
La definizione dice: L appartiene a NP-HARD se, per ogni L' appartenente ad NP, esiste una riduzione polinomiale da L' a L.
Questo vuol dire che il linguaggio L sarà almeno difficile quanto L'.
In termini di insiemistica, la classe NP-COMPLETE può essere rappresentata come intersezione di due classi, cioè di NP e NP-HARD.

Nella prossima puntata (per la serie ipse dixit) parlerò della riduzione tra problemi.

Molto utile Grazie...

Ottima guida A tempo perso darò anche io il mio contributo

Carmine ha scritto:

Ottima guida A tempo perso darò anche io il mio contributo

oooh si bravissimo!
Potremmo dividerci gli argomenti e trovare qualche altra anima pia che voglia cimentarsi in quest' opera!

complimenti.. finalmente ho capito anch'io... maledetto libraccio... mi perdo nel libroooooo

ladydarko ha scritto:

complimenti.. finalmente ho capito anch'io... maledetto libraccio... mi perdo nel libroooooo

Grazie..

Mi dispiace solo non aver potuto scrivere altro causa inesistenza di tempo disponibile...

Altro che P=NP.. trovare tempo è un problema peggiore!