Calcolabilità e Complessità : classi di complessità

Utente Junior Età : 21 Registrato il : 23/01/08 Messaggi : 341

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.

Primi Passi Registrato il : 07/01/08 Messaggi : 97 Localizzazione : Castlevania

Molto utile Grazie...
_________________
A. Einstein: "Tutti sanno che una cosa é impossibile da realizzare, finché arriva uno sprovveduto che non lo sa e la inventa"

Ottima guida lol!

A tempo perso darò anche io il mio contributo Very Happy

_________________
Quando la massa vede in te un Pazzo e folli le cose che dici, folli le cose che pensi, folli le cose che fai, allora sorridi e guardandoti allo specchio inchinati: sei davanti a un Genio.
Perchè coloro che sono abbastanza folli da pensare di cambiare il mondo, sono quelli che poi lo fanno...

Utente Junior Età : 21 Registrato il : 23/01/08 Messaggi : 341

complimenti.. finalmente ho capito anch'io... maledetto libraccio... mi perdo nel libroooooo
_________________
con arco e frecce catturo anime...

Utente Junior Età : 21 Registrato il : 23/01/08 Messaggi : 341