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 » 14.NP-Completezza - prima parte


Introduzione

I problemi NP-completi formano un’importante sottoclasse di NP.

Il concetto della NP-completezza è stato studiato nei primi anni del 1970 da Stephen Cook e Leonid Levin.

Se esistesse un algoritmo in tempo polinomiale per tutti i problemi NP-completi, allora tutti i problemi NP sarebbero risolvibili in tempo polinomiale.

Per dimostrare che P = NP è sufficiente prendere un particolare problema NP-completo A e dimostrare che A∈P.

Per dimostrare che P ≠ NP è sufficiente prendere un particolare problema NP-completo A e dimostrare che A∈P.

Sul lato pratico, sapere che un dato problema A è NP-completo può evitare di perdere tempo alla ricerca di un (forse inesistente e comunque “difficile” da trovare) algoritmo polinomiale per A.

Un problema in NP: le formule Booleane

Variabili booleane: x,y,… tale che possono assumere uno dei due seguenti valori 0 (false), 1(true).

Operatori booleani: ⌉ (NOT), ∧ (AND), ∨ (OR).

Formule booleane: sono costruiti con le variabili e le operazioni nel modo standard. Una volta che un assegnamento di verità per le variabili è dato, il valore di una formula composta è calcolato come segue:

0 0 = 0 …………….0 0 = 0
0
1 = 0 …………….0 1 = 1
1
0 = 0 …………… 1 0 = 1
1
1 = 1 …………… 1 1 = 1

Problema Sat

Si dice che una formula booleana è soddisfacibile se e solo se vi è una assegnamento di 0 e 1 per le sue variabili che rende la formula composta vera (valutata 1).
Le seguenti formule sono soddisfacibili?

x(xy)
x
(xy)

Il problema Sat consiste nel trovare un assegnamento tale che la formula φ risulti vera:
SAT = {<φ> | φ è una formula booleana soddisfacibile}

SAT P?
SAT NP?

Theorem 7.27 (Cook-Levin theorem) SATP sse P=NP.

Riducibilità in tempo polinomiale

Definizione: Una funzione calcolabile in tempo polinomiale è una funzione calcolabile in tempo polinomiale da una Macchina di Turing deterministica.

Definizione di Mapping riducibilità polinomiale: Siano A e B due linguaggi con alfabeto Σ. Diremo che A è Mapping riducibile in tempo polinomiale a B, o semplicemente riducibile in tempo polinomiale a B, e scriveremo A≤PB, se esiste una funzione calcolabile in tempo polinomiale f: Σ* → Σ* t.c. per ogni stringa wΣ*,

wA   sse   f(w)B.

Tale funzione f è chiamata riduzione in tempo polinomiale da A a B.

Una condizione sufficiente per P

Teorema: Se A≤PB e BP, allora AP.

Dimostrazione:
Assumiamo che esiste una MdT M in grado di decidere B in tempo polinomiale. Sia f una riduzione in tempo polinomiale da A a B.
Il seguente è un algoritmo polinomiale per decidere A:

  • N = “Con w in input:
    1. Calcola f(w).
    2. Simula M su ingresso f(w) e accetta se e solo se M accetta”
  • Chiaramente N lavora in tempo polinomiale perché è la composizione di due azioni, entrambe svolte in tempo polinomiale.

Problema 3SAT

Un letterale è una variabile Booleana x o la sua negata x.

Una clausola è un insieme di letterali connesso con operatori Booleani. Per semplicità, ci limiteremo al simbolo OR (∨). Per esempio (x y z t) è una clausola.
Una formula Booleana è in forma normale congiuntiva (conjunctive normal form), chiamata anche cnf-formula, se comprende numerose clausole connesse dal simbolo AND (∧), per esempio:

(x y z t) (x z) (x y t)

È una formula in CNF.
Una cnf-formula è detta 3cnf-formula se tutte le sue clausole hanno 3 letterali, per esempio

(x y z ) (x z t) (x y t) (z y t)

è una 3cnf-formula.

Definizione problema 3Sat:
3SAT = {<φ> | φ è una 3cnf-formula soddisfacibile}

Riduzione di 3SAT a CLIQUE

Teorema: 3SAT è riducibile in tempo polinomiale a CLIQUE.

Dimostrazione: Sia φ una 3CNF-formula con k clausole, ovvero

φ = (a1 b1 c1) (a2 b2 c2) (ak bk ck)

La nostra riduzione f consiste nel generare la stringa dove G è un grafo non orientato definito come segue:
I nodi di G sono organizzati in k gruppi, t1, …, tk, ognuno dei quali di tre nodi e chiamati triple.
Ciascuna tripla corrisponde ad una clausola di φ,
Ciascun nodo della tripla corrisponde ad un letterale della clausola ad esso associata.
Etichettiamo ciascun nodo di G con il letterale ad esso associato.

Riduzione di 3SAT a CLIQUE (segue)


Riduzione di 3SAT a CLIQUE (segue)


Riduzione di 3SAT a CLIQUE (segue)


Definizione di NP-COMPLETEZZA

Definizione Np-complete: Un linguaggio B è NP-complete se soddisfa le seguenti due condizioni:

  1. B è in NP, e
  2. Ogni linguaggio in NP è riducibile in tempo polinomiale a B.

Teorema: Se un linguaggio B è in NP-complete e BP, allora P=NP.

Definizione di NP-COMPLETEZZA (segue)

Teorema: Se CNP, B è NP-complete e B≤PC, allora C è NP-complete.

Dimostrazione:
Sappiamo che C NP, quindi abbiamo solo bisogno di dimostrare che APC per ogni A NP.

Siccome B è NP-completo, per definizione abbiamo che APB,

Supponiamo che f è una funzione di riduzione da A a B.

Supponiamo che B PC e che g è la funzione di riduzione polinomiale da B a C.

Costruiamo ora h come la composizione di f e g, t.c., h(w) = g(f(w)).

h è la composizione di due funzioni polinomiali, dunque è anch’essa polinomiale, ed è una riduzione da A a C. Quindi APC.

NP-completezza di 3SAT

Teorema: 3CNF è NP-completo

Dimostrazione. Dalla logica, una funzione computabile polinomiale

f: {<α> | α è una formula booleana} → {<α> | α è una 3cnf-formula}

è tale che, per ogni formula Booleana α,

α è soddisfacibile se f(α) è soddisfacibile.

Allora, f è una riduzione in tempo polinomiale da SAT a 3CNF.

Nella prossima lezione dimostriamo che SAT è NP-completo.

[Esercizio per gli studenti]: Usando il fatto che SAT è NP-completo, dimostrare che 3CNF è NP-completo.

  • 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