Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 15.NP-Completezza - seconda parte


Definizione di NP-COMPLETEZZA

Si ricordi che un linguaggio B è NP-complete se soddisfa le seguenti due condizioni:

  1. B è in NP,
  2. 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 SATNP è 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 sC, 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.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion