Riassunto esame Teoria della calcolabilità e complessità, Prof. Mignosi Filippo, libro consigliato Automi, linguaggi e calcolabilità, Rajeev Motvani

L

ne □

Teorema 9.8 (L non R) L non è ricorsivo.

ne ne □

Dimostrazione 18 (L non R) Costruisco una TM M’ composta da una sotto-macchina M che prende un

ne

input w: se M accetta (non accetta) w, allora M’ accetta (non accetta) ogni input. Questa è una riduzione

perché:

• ∗ ∗ ′ ′

∀x ∈ ∈

Se M accetta w, M’ accetta Σ , quindi Σ = L(M ) e M L .

ne

• ∗ ′ ′

∀x ∈ ∅ ̸∈

Se M non accetta w, M’ non accetta Σ , quindi = L(M ) e M L .

ne

M’ compie le seguenti azioni: {q }.

1. Ignora l’input x. Se n è la lunghezza della stringa (M,w), allora Q = , q , ..., q Nello stato q , M’

0 1 n i

scrive l’(i+1)-esimo bit di (M,w), va nello stato q e si muove a destra. Se nello stato q incontra altri

i+1 n

simboli li sostituisce con blank.

2. Quando M’ trova un blank nello stato q , ricolloca la testina a sinistra del nastro.

n

3. Con stati aggiuntivi, M’ simula una TM universale sul nastro corrente.

4. Se U accetta, accetta anche M’. Se U non accetta mai, allora non accetta mai neanche M’.

Siamo riusciti a ridurre L a L , quindi dato che L è indecidibile (non R), allora anche L è indecidibile

u ne u ne

(non R). □

Teorema 9.9 (L non RE) L non è RE.

e e □

Dimostrazione 19 (L non RE) Sapendo che L è RE ma non R, se L fosse RE allora entrambi sarebbero

e ne e

R, quindi L non può essere RE.

e □

25

9.8 Teorema di Rice

La distinzione in L ed L è solo un caso specifico di un teorema più generale. Una proprietà è un insieme di

e ne

linguaggi con caratteristiche comuni e, in particolare:

Definizione 9.7 (Proprietà non banale) Una proprietà si dice non banale se l’insieme dei linguaggi che la

rispettano non è né vuoto né uguale all’insieme di tutti i linguaggi RE. In altre parole, una proprietà è non

banale se esiste almeno un linguaggio che la rispetta e almeno un linguaggio che non la rispetta. □

Teorema 9.10 (Teorema di Rice) Tutte le proprietà non banali dei linguaggi RE sono indecidibili. □

Se dimostriamo quindi che la proprietà di un linguaggio è non banale, allora dimostriamo che il problema è

indecidibile. P

Dimostrazione 20 (Teorema di Rice) Sia una proprietà non banale dei linguaggi RE, e sia L l’insieme

P

∈ P,

dei codici di TM M tali che L(M ) allora dividiamo in due casi:

i i

∅ ̸∈ P, ̸ ∅ P

1. quindi deve esistere un L = che sia in e una macchina M che lo accetta. Per dimostrare che

L

P è indecidibile eseguiamo una riduzione da L a L tramite una TM M’ che simula (M,w) (input della

P

u

riduzione) su U, quindi:

• ∈

∈ , inizia l’esecuzione di M su x che accetta se x L, quindi M’

Se U accetta, quindi (M, w) L L

u ′

∈ ∈ P ∈

accetta se x L, ovvero L(M’) = L e M L .

P

• ̸∈ ̸∈

Se U non accetta, quindi (M, w) L , M non fa nulla e quindi x L, quindi M’ non accetta se

u L

′

̸∈ ∅ ̸∈ P ̸∈

x L, ovvero L(M’) = e M L .

P

Dato che l’algoritmo trasforma (M,w) in una M’ che è in L se e solo se (M,w) è in L , allora esso è

P u

P

una riduzione da L a L , quindi è indecidibile.

P

u P

∅ ∈ P che è anch’esso indecidibile. Vale che L = L . Se

2. Esaminiamo ora il caso in cui e valutiamo P P

fosse decidibile, allora dovrebbe esserlo anche L ma abbiamo dimostrato che non lo è.

L P

P □

26

Secondo Parziale 27

10 Intrattabilità

Abbiamo definito cosa è calcolabile, ma in questo capitolo cercheremo di capire cosa lo è in modo efficiente. I

problemi decidibili possono essere classificati in gruppi a seconda dell’ordine di grandezza del tempo che la TM

che li computa impiega. In particolare, la distinzione tra problemi decisionali concreti che richiedono tempo

polinomiale e quelli che richiedono tempo esponenziale o più è fondamentale poiché quest’ultimi non possono

generalmente essere risolti. Con la teoria dell’intrattabilità cerchiamo di dimostrare (tramite congetture supposte

vere) che un certo problema non può essere risolto in tempo polinomiale.

P N P

10.1 Classi e P N P,

Le prime due classi di problemi decisionali concreti calcolabili che introduciamo sono le classi e ovvero:

• P: insieme dei problemi risolvibili in tempo polinomiale da una TM deterministica.

• N P: insieme dei problemi risolvibili in tempo polinomiale da una TM non deterministica.

P ⊆ N P,

Dato che una DTM è una NTM con una possibile scelta per ogni mossa, vale che mentre la relazione

N P

inversa è un problema ancora aperto: sembra infatti che non esistano problemi appartenenti a ma non a

P. Si dice che una TM ha complessità in tempo T(n) se per un input w di lunghezza n, M si arresta dopo al

più T(n) mosse. P) ∈ P

Definizione 10.1 (Classe Un linguaggio L se esiste un polinomio T(n) tale che L = L(M) e M è una

deterministica di complessità T(n). □

N P) ∈ N P

Definizione 10.2 (Classe Un linguaggio L se esiste un polinomio T(n) tale che L = L(M) e M

è una non deterministica di complessità T(n). □

10.2 Riduzioni polinomiali

Utilizziamo la riduzione polinomiale per dimostrare che se un problema non è polinomiale allora non lo è neanche

un altro.

Definizione 10.3 (Riduzione polinomiale) Una riduzione polinomiale da P a P è una funzione f tale che:

1 2

• f è calcolabile da una TM in tempo polinomiale.

• ∈ ⇔ ∈

x L(P ) f (x) L(P ).

1 2 □

P

Teorema 10.1 (Teorema 0) Se esiste una riduzione polinomiale da P a P , allora se P è in lo è anche

1 2 2

P .

1 □

Dimostrazione 21 (Teorema 0) Dato che sia l’algoritmo per la riduzione che quello per risolvere P sono

2

polinomiali, la loro concatenazione sarà ancora polinomiale. Per lo stesso principio della dimostrazione della

riduzione classica, allora anche P può essere risolto in tempo polinomiale tramite questa concatenazione.

1 □

10.3 Problemi NP-completi e NP-hard

N P-complete) ∈ N P-complete

Definizione 10.4 (Classe Un linguaggio L se:

• ∈ N P.

L

• ′ ′

∈ N P

Per ogni L esiste una riduzione polinomiale di L a L. □

28 ∈ N P-complete ∈ N P,

Teorema 10.2 (Riduzione da NP-completo a NP) Sia P e P se esiste una

1 2

∈ N P-complete.

riduzione polinomiale da P a P , P

1 2 2 □

N P, ∈ N P-

Dimostrazione 22 (Riduzione da NP-completo a NP) Sia L un qualsiasi allora dato che P 1

complete, esiste riduzione polinomiale da L qualsiasi a P . Sapendo inoltre che esiste una riduzione da P a

1 1

N P)

P , allora concatenando le due riduzioni otteniamo una nuova riduzione polinomiale da L qualsiasi (∈ a

2 N P-completo.

P , quindi P è

2 2 □

N P-completo,

Questo teorema ci permette, una volta dimostrato che almeno un problema è di dimostrare che

una serie di altri problemi lo sono semplicemente riducendo il primo ad ognuno di essi.

P N P) N P-completo

Teorema 10.3 (Condizione di equivalenza tra e Se esiste un problema P che sia

P, P N P.

anche in allora = □

P N P) ∈ N P-complete ∈

Dimostrazione 23 (Condizione di equivalenza tra e Supponiamo che P e P

P, N P ∈ P ∈ P.

allora ogni linguaggio in si riduce in tempo polinomiale a P, quindi P e anche L □

N P-hard) ∈ N P-hard

Definizione 10.5 (Classe Un linguaggio L se è possibile dimostrare la condizione 2

N P-complete, ∈ N P).

della definizione di ma non la condizione 1 (L □

10.4 Problema SAT N P-completezza.

Il problema della soddisfacibilità è un problema per cui esiste un teorema che enuncia la sua N P-

Utilizzeremo tale problema come base per la riduzione ad altri problemi, per dimostrare anche la loro

completezza.

10.4.1 Definizione di SAT

Data un’espressione booleana E è costruita a partire da variabili booleane, operatori binari, unari e paren-

tesi. Un’espressione si dice soddisfatta da un certo assegnamento di valori alle sue variabili T se E(T) = 1.

Un’espressione E si dice soddisfacibile se esiste almeno una T che soddisfa E.

Definizione 10.6 (Problema SAT) Il problema SAT consiste nel determinare se un’espressione booleana E

è soddisfacibile. □

Enunciato come linguaggio, SAT corrisponde all’insieme delle espressioni booleane codificate soddisfacibili. Per

rendere SAT un problema decisionale concreto, basta aggiungere un pedice intero alle variabili e renderle finite,

quindi l’alfabeto sarà composto da {∧, ∨, ¬, (, ), x, 0, 1}

con cui ogni variabile è rappresentata come ’x’ seguito dall’indice codificato in binario.

N P-completezza

10.4.2 di SAT

P-completezza N P-completo

L’N di SAT è enunciata dal teorema di Cook. Questo teorema dimostra che SAT è

N P

riducendo ogni problema ad esso. N P-completo.

Teorema 10.4 (Teorema di Cook) SAT è □

∈ N P:

Dimostrazione 24 (Teorema di Cook (prima parte)) Proviamo che SAT

29

1. Una componente non deterministica ”tenta” assegnamenti per l’espressione in tempo lineare nel seguente

modo:

• Enumero le variabili dell’espressione.

• Scrivo in un nastro tante stelline quante sono le variabili.

• {0,

Sostituisco ogni stellina con un valore in 1}. n

Dato che la NTM può compiere due scelte per ogni variabile, dopo n passi posso esplorare 2 ID distinte.

2. Valuto E con l’assegnamento scelto, quindi accettiamo se E(T) = 1. Per accettare basta quindi che esista

almeno un assegnamento che soddisfa E. 2

L’intero riconoscimento di SAT da parte della NTM multinastro può essere fatto in O(n ), quindi per una

4

mononastro è sufficiente O(n ). □

∈ P), N P

Se esistesse un decisore deterministico per SAT (ovvero SAT allora dato che tutti gli possono essere

N P P.

ridotti a SAT, tutti gli sarebbero anche

10.5 Estensioni di SAT P-completezza.

Esistono dei sotto problemi di SAT di cui dimostreremo l’N In generale, se un problema è

N P-completo non possiamo dire nulla sui suoi sotto problemi.

10.5.1 Forme normali di espressioni booleane

Utilizziamo le seguenti due definizioni:

• x.

Letterale: variabile (x) o variabile negata

• ∨

Clausola: disgiunzione logica (OR = / +) di uno o più letterali.

Un’espressione booleana è in:

• ∧ ·)

Forma normale congiuntiva se è la congiunzione logica (AND = / di una o più clausole.

• Forma normale k-congiuntiva se è la congiunzione logica di una o più clausole composte da k letterali

distinti.

Affrontiamo quindi i du