Definizione di NP-COMPLETEZZA
Si ricordi che un linguaggio B è NP-complete se soddisfa le seguenti due condizioni:
- B è in NP,
- Ogni linguaggio in NP è riducibile in tempo polinomiale a B. (hardness).
Teorema di Cook-Levin inizio
Teorema: SAT è in NP-complete.
Dimostrazione:
- [Appartenenza a NP]: Che SAT ∈ NP è ovvio (esercizio per gli studenti).
- [Hardness]: Dimostriamo adesso che ogni linguaggio A in NP è riducibile in tempo polinomiale a SAT.
- Sia A un arbitrario linguaggio tale che A ∈ NP.
- Sia N la macchina di Turing non deterministica che decide A.
- Se A ∈ NP, allora il tempo di esecuzione di N è dell’ordine di nk, dove n è la dimensione dell’input.
- Mostriamo come trasformare una stringa w in una formula booleana φ che “simula” N su input w, nel senso che φ è soddisfacibile se e solo se N accetta w.
Teorema di Cook-Levin: Tableaux
Un tableau per N su w è una tabella nkx nk le cui righe sono le configurazioni di un ramo di calcolo di N su input w = w1 … wn. La prima e ultima colonna contengono solo “#”.
Un tableau è accettante se una delle sue righe è una configurazione accettazione.
Ogni tableau accettante per N su w corrisponde ad un ramo accettante di N su input W.
Quindi, determinare se N accetta w equivale a determinare se c’è un tableau accettante per N su w.
Teorema di Cook-Levin: φ
Sia C l’insieme Q ∪ ∑ ∪ {#}, dove Q è l’insieme degli stati di N e ∑ è l’alfabeto del nastro. C è dunque l’insieme di tutti i possibili contenuti delle celle del tableau.
La cella nella riga i e colonna j è chiamata cell[i,j].. Per ogni cella e per ogni s∈C, si crea una variabile booleana xi,j,s. Il suo significato è “la cell[i,j] contiene il simbolo s”.
La formula Φ si costruisce con queste variabili nel modo seguente:
Φ = Φcell ∧ Φstart ∧ Φmove ∧ Φaccept
- Φcell asserisce che ciascuna cella contiene esattamente un simbolo.
- Φstart asserisce che la prima riga è la configurazione iniziale su input w.
- Φmove asserisce che le righe sono create “legate” le une dalle altre in conformità con la funzione di transizione.
- Φaccept asserisce che una cella contiene uno stato di accettazione.
- Φquindi asserisce che il tableau è un ramo di accettazione della computazione, ovvero che w∈A.
Teorema di Cook-Levin: φcell
Teorema di Cook-Levin: φstart
Teorema di Cook-Levin: φaccept
Teorema di Cook-Levin: finestre (windows)
Teorema di Cook-Levin: esempi di finestre legali e non
Il teorema di Cook-Levin: Domanda sulle Windows
Claim: Se la riga superiore del tableau è la configurazione iniziale e tutte le finestre nel tableau sono legali, allora ogni riga del tableau è una configurazione che legalmente segue quella precedente.
Dimostrazione:
Si prendano in esame ogni due righe adiacenti (configurazioni).
Nella configurazione superiore, ogni cella che non è adiacente al simbolo di uno stato e non contiene il simbolo di limite # è il simbolo di una cella in una finestra di tre celle la cui parte centrale non è interessata da transizioni di N.
Pertanto quel simbolo centrale, in una finestra legale, non deve cambiare nella parte inferiore della finestra (figura in alto).
La finestra superiore che invece contiene nella parte centrale uno stato, sicuramente sarà interessato da una transizione.
Le corrispondenti tre posizioni nella parte inferiore saranno aggiornate in base alla funzione di transizione.
Pertanto, se la configurazione superiore è una configurazione legale, allora è una configurazione legale anche quella inferiore (figura in basso).
Teorema di Cook-Levin: φmove
Teorema di Cook-Levin: φmove (segue)
La nostra riduzione costruisce φ e la sua complessità di tempo è asintoticamente la stessa della dimensione di φ.
È importante verificare che questa dimensione è polinomiale nella dimensione n macchina di Turing N.
Per la costruzione data, è sufficiente verificare la polinomialità (in n) dei quattro congiunzioni di φ.
Qual’è la taglia di φstart?
Qual’è la taglia di φaccept?
Qual’è la taglia di φcell?
Qual’è la taglia di φmove?
La complessità della riduzione risulta essere O(n2k), dunque la riduzione è polinomiale.
Nota: Se invece delle finestre avessimo preso in considerazione due intere configurazioni, allora la complessità di move sarebbe stata di Cnk, dunque esponenziale.
Le lezioni del Corso
4. Macchine di Turing multinastro
5. Macchine di Turing non-deterministiche
6. Macchina di Turing universale e problema della fermata
7. Problemi decidibili e non decidibili
8. Problemi non decidibili e riducibilità - prima parte
9. Problemi non decidibili e riducibilità - seconda parte
11. Decidibilità delle teorie logiche
12. Misurazione della Complessità e introduzione alla classe P
14. NP-Completezza - prima parte
15. NP-Completezza - seconda parte
16. Altri problemi NP-Completi
17. Esercitazione su problemi NP-Completi
18. Space Complexity
19. Savitch Theorem
