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 particolareproblema 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 nelmodo 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∧(x∨y)
x∧(x∨y)

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) SAT∈P 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∈Σ*,

w∈A   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 B∈P, allora A∈P.

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

φ = (a₁∨ b₁∨ c₁) ∧ (a₂∨ b₂∨ c₂) ∧ … ∧ (a_k∨ b_k∨ c_k)

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, t₁, …, t_k, 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 B∈P, allora P=NP.

Definizione di NP-COMPLETEZZA (segue)

Teorema: Se C∈NP, B è NP-complete e B≤_PC, allora C è NP-complete.

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

Siccome B è NP-completo, per definizione abbiamo che A≤_PB,

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 A≤_PC.

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.