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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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