1

Riduzioni di Turing

! Nozione più forte di riduzione polinomiale

tra linguaggi.

! Basata sul modello di calcolo della

macchina di Turing con oracolo (OMdT).

2

OMdT

! MdT dotata di un nastro addizionale:nastro di oracolo.

! Ad ogni OMdT è associato un linguaggio,detto insieme di oracolo.

! Stato speciale, qASK, detto stato didomanda.

3

OMdT

! Nello stato qASK viene scritta una stringasul nastro di oracolo:

! l'oracolo confronta la stringa scritta sulnastro di oracolo con l'insieme di oracolo;

! risponde SI o NO (scrivendo sul nastro dioracolo) a seconda che la stringa appartengao meno all'insieme di oracolo.

4

OMdT

! Non ci sono limiti al numero di volte per

cui è consentito interrogare l'oracolo, se

non quelli dettati dalla limitazione al

numero di passi della computazione.

! Ipotesi: la risposta dell'oracolo è

istantanea.

5

Definizione

L’insieme A è Turing- (o Cook-) riducibile

in tempo polinomiale all'insieme B,

A ! pT B

se esiste una OMdT M con oracolo per B

che accetta A in tempo polinomiale.

6

Teorema: Proprietà delle riduzioni diKarp

Siano A, B e C tre insiemi. Valgono leseguenti relazioni:

! A !mp A

! A !mp B ! B !m

p C " A !mp C

! A !mp B ! B # P " A # P

! A !mp B ! B # NP " A # NP

7

Teorema: Proprietà delle riduzioni diTuring-Cook

Siano A e B due insiemi. Valgono leseguenti relazioni:

! A !Tp C(A)

! A !Tp B ! B # P " A # P

8

Osservazione

! Da A !Tp B ! B # NP non possiamo

inferire che A # NP.

9

Equivalenza e gradi

! Se A !mp B e B !m

p A si dice che A e B

sono equivalenti rispetto a !mp:

A $mp B.

! La relazione $mp è una relazione di

equivalenza.

10

Equivalenza e gradi

! Se A !Tp B e B !T

p A si dice che A e B

sono equivalenti rispetto a !Tp:

A $Tp B.

! La relazione $Tp è una relazione di

equivalenza.

11

I problemi NP-completi! Le riduzioni limitate in tempo polinomiale sono state

utilizzate per individuare i problemi più difficili

all'interno della classe NP (ragionevoli candidati a non

appartenere alla classe P).

! Nella classe NP è possibile individuare una classe diproblemi, i problemi completi, la cui appartenenza a Pimplicherebbe:

P = NP.

12

Definizione

Un insieme A si dice completo per NP

rispetto a !mp , o NP-completo se:

! A # NP,

! per ogni B # NP, B !mp A.

13

Problemi NP-completi

! Dimostrare l'uguaglianza P = NP coincidecon esibire un algoritmo deterministico dicosto polinomiale per un problema NP-completo

da questo algoritmo (tramite le riduzioni) siavrebbero automaticamente algoritmideterministici di costo polinomiale per tutti iproblemi in NP.

14

Problemi NP-completi

Viceversa dimostrare che P % NP è

equivalente a dimostrare che un problema

NP-completo non appartiene alla classe P.

15

Problemi NP-completi

L'esistenza di problemi completi per NP

costituisce un indizio a favore della

congettura P % NP:

falsificare la congettura vorrebbe diredimostrare che esistono algoritmi efficienti perun’ampia classe di problemi per cui, finora, nonsembra possibile sfuggire alla ricerca esaustiva!

16

Problemi NP-completi

La definizione di NP completezza sembra a

prima vista poco utilizzabile in pratica:

dimostrare che un linguaggio è NP-completo

significa stabilire che tutti i linguaggi in NP

gli si riducono in tempo polinomiale.

17

Il risultato di Cook

! Steve Cook (1971) ha dimostrato che il problema

decisionale della soddisfattibilità di una sequenza

di clausole booleane (SAT) è NP-completo.

! Data una formula booleana espressa in forma

normale congiuntiva (AND di OR), il problema SAT

consiste nel dire se esiste un assegnamento di

verità alle variabili per cui la formula è vera.

18

Teorema di Cook

Il problema SAT è NP-completo.

19

Dimostrazione (cenni)

! Per prima cosa occorre dimostrare cheSAT # NP:

ogni istanza positiva di SAT è certificata daun assegnamento di verità, che consiste inuna stringa lunga quanto il numero divariabili della formula;

20

Dimostrazione (cenni)

! La verifica può essere eseguita in tempo lineare nella lunghezza

della formula:

! i-esima variabile della formula xi & l' i-esimo bit del

certificato

! j-esima variabile complementata ¬xj & complemento del j-

esimo bit del certificato.

! In questo modo la formula viene trasformata in un'espressione

che coinvolge solo le due costanti e le operazioni logiche AND e

OR, e che può essere valutata banalmente.

21

Dimostrazione (cenni)

! La parte difficile della dimostrazione consiste nel far

vedere che qualsiasi linguaggio L # NP si riduce a SAT.

! Ogni linguaggio in NP può essere descritto in modo standard,

fornendo una MdTN che lo riconosce in tempo polinomiale.

! Questo consente di lavorare con una generica macchina M e

di derivare una trasformazione polinomiale generica dal

linguaggio LM a SAT.

! La riduzione costruisce, per ogni input x, una formula

booleana f(x) soddisfattibile se e solo se x # LM . �

22

Osservazioni

! La classe dei problemi NP-completi (NPC)

contiene problemi naturali.

! Il Teorema di Cook fornisce una metodologia

per dimostrare agilmente la NP-completezza

di problemi diversi da SAT.

23

Lemma

Siano A e B due insiemi che appartengono

alla classe NP. Se A # NPC e A !mp B,

allora B # NPC.

24

Dimostrazione

! Poiché B # NP, dobbiamo solo verificare che, perogni C # NP, C !m

p B.

! Dato che A # NPC, allora C !mp A, per ogni C #NP.

! La transitività delle trasformazioni polinomiali eil fatto che A !mp B, implicano C !mp B, per ogniC # NP.

�

25

Problemi NP-hard

! Esistono problemi a cui tutti i problemi in NP si

riducono in tempo polinomiale, ma per i quali non

sono note dimostrazioni di appartenenza a NP.

! Problemi con queste caratteristiche sono detti

NP-hard, ad indicare che sono “almeno difficili”

quanto i problemi NP-completi.

26

Definizione alternativadi NP-completezza

Un insieme A # NP è NP-completo se

SAT !mp A.

27

Problemi NP-completi: esempi

3SAT è NP-completo.

La dimostrazione consiste nel mostrare come ogni istanza

di SAT possa essere ricondotta al caso di un'istanza con

solo tre termini per clausola:

! Il numero di clausole dell'istanza di 3SAT così ricavata

è polinomiale nel numero di clausole originarie;

! l’istanza può essere calcolata in tempo polinomiale

! ed è soddisfattibile se e solo se lo è l'istanza di

partenza.

28

Problemi NP-completi: esempi

Acquisita la NP-completezza di 3SAT, le

riduzioni da 3SAT a CLIQUE e da 3SAT

a IND, dimostra che anche i problemi

CLIQUE e IND sono NP-completi.

29

Cammino hamiltoniano

CH dire se in un grafo esiste un camminohamiltoniano, ossia un cammino che visitatutti nodi una volta sola.

CH è NP-completo.

30

TSP

Il TSP è NP-completo.

31

Dimostrazione (cenni)

Riduzione da CH:! Dato un grafo G con n nodi, si costruisce

un'istanza del TSP con n città (ogni cittàcorrisponde ad un nodo del grafo) e una opportunamatrice delle distanze D;

! si determina un intero k tale che esiste uncammino di lunghezza al più k rispetto a D se esolo se G possiede un cammino hamiltoniano.

32

Dimostrazione (cenni)

! La matrice D viene costruita come segue:

! la distanza tra due città i e j viene posta ad 1 se

(i, j) è un arco di G e a 2 altrimenti.

! Ponendo k = n, si ottiene la riduzione cercata:

! se il grafo non ha cammini hamiltoniani, si deve

inserire nel percorso un tratto di lunghezza 2

(vista la mancanza dell'arco in G) e quindi si

supera la soglia n;

33

Dimostrazione (cenni)

viceversa, se la lunghezza del percorso è n,

significa che

! è stato possibile individuare il percorso esclusivamente su

archi del grafo (ciascuno dei quali corrisponde a tratti di

lunghezza 1 del percorso)

! quindi il grafo deve contenere almeno un cammino

hamiltoniano. �

34

Colorazione di grafi

COL:consiste nel chiedersi se sia possibile “colorare”i vertici di un grafo utilizzando al più k colorie in modo tale che vertici adiacenti nel grafovengano colorati con colori diversi.

COL è NP-completo (anche per k = 3).

35

La struttura della classe NP

Nell’ipotesi in cui P % NP,

NP = P ' NPC

oppure esistono in NP anche linguaggi di

difficoltà intermedia tra quelli facili (P)

e quelli difficili (NPC) ?

36

Teorema

Se P % NP esistono insiemi in NP \ P

che non sono completi rispetto alle

riduzioni di Turing-Cook.

37

Teorema

Se P % NP esistono insiemi in NP \ P che

non sono completi rispetto alle riduzioni

di Karp.

38

Osservazioni

! La classe NPI = NP \ (P ' NPC) non è

vuota se P % NP.

! Se P % NP, la classe NPI è composta da

una gerarchia infinita di classi distinte di

insiemi di difficoltà intermedia tra P e

NPC.

39

Classi relativizzate

! Sono classi di linguaggi riconosciuti da opportune

macchine dotate di oracolo, definite sfruttando le

riduzioni di Turing.

! In ambito non deterministico le classi

relativizzate sono basate sulla OMdT non

deterministica (OMdTN):

una MdTN che dispone di un oracolo, in grado di

decidere l'insieme di oracolo come nel caso della OMdT.

40

Classi relativizzate

Un linguaggio L si riduce (in tempo

polinomiale) non deterministicamente a L’

L !NTp L’

se L può essere riconosciuto in tempo

polinomiale da una OMdTN con un

oracolo per L’.

41

Classi relativizzate

La relativizzazione di P e NPcorrisponde potenziare rispettivamente laMdT e la MdTN polinomiali, consentendol'accesso ad un oracolo:

PY = { L | ) L’ # Y t.c. L !Tp L' }

NPY = { L | ) L’ # Y t.c. L !NTp L' }

42

Classi relativizzate

! Supponiamo che, date le classi X ( Y,

esistano due insiemi di oracolo A e B tali che

XA = YA e XB % YB

! Si potrebbe pensare che se esiste un oracolo

B per cui XB % YB allora debba essere X % Y.

! Ma questo risulta falso!

43

Classi relativizzate

! Il fatto che due oracoli abbiano, rispetto adue classi, azioni di effetto opposto mettein rilievo che il confronto tra X e Y è moltodifficile:

le tecniche di dimostrazione ad oggi conosciute

possono dimostrare che X % Y soltanto se vale

XC % YC, per ogni insieme di oracolo C.

44

Classi relativizzate

! Le tecniche note per dimostrare risultati di

separazione (come la diagonalizzazione e la

simulazione passo passo) relativizzano.

! Tali tecniche non consentono di dimostrare

che X % Y, se esistono due oracoli A e B

tali che XA = YA e XB % YB.

45

Non relativizzazione delconfronto tra P e NP

Questo è proprio il caso delle classi

P e NP, per le quali si possono

costruire due linguaggi A e B tali

che PA = NPA e PB % NPB.

46

La gerarchia polinomiale

Può essere utilizzata per classificare

problemi per cui non si conoscono algoritmi

polinomiali (sia deterministici che non

deterministici), ma per i quali

esisterebbero algoritmi deterministici

polinomiali se P = NP.

47

Gerarchia polinomiale

Consiste nell'unione delle classi *kp, +k

p , ,kp,

che formano il k-esimo livello dellagerarchia, dove:

*0p = +0

p = ,0p = P,

e, per ogni k " 0,*k+1

p = P^(+kp)

+k+1p = NP^(+k

p),k+1

p = co+k+1p

48

La gerarchia polinomiale

La gerarchia polinomiale PH può essere

definita come

!

PH =j= 0

"

#$ j

p

49

Primi livelli di PH

*1p = P, +1

p = NP, ,1p = coNP

*2p = PNP, +2

p = NPNP, ,2p = co(NPNP)

50

Primi livelli di PH

! Al primo livello vi sono i problemi risolvibili intempo polinomiale deterministico o nondeterministico (P e NP) o il cui complemento èrisolvibile in tempo polinomiale nondeterministico (coNP);

! Al secondo livello vi sono i problemi risolvibili intempo polinomiale tramite opportune macchineche dispongono di un oracolo per il primo livello.

51

Primi livelli di PH

! Se P = NP, PH collassa su P: PH = P.

! Se P % NP, allora PH è candidata a

contenere problemi di difficoltà crescente

con il livello della gerarchia a cui

appartengono.

52

Relazioni di inclusione

,kp - +k

p ( *k+1p ( ,k+1

p - +k+1p ( *k+2

p

(Non è noto se le inclusioni siano proprie.)

53

Problemi aperti

I tre problemi aperti! è vero che +k

p % +k+1p, per ogni k " 0 ?

! è vero che +kp % ,k

p, per ogni k " 1 ?! è vero che *k

p % ,kp - +k

p, per ogni k " 1 ?generalizzano le tre principali congetture cheruotano intorno alle classi P e NP:

P % NPNP % coNPP % NP - coNP

54

Problemi di ottimizzazione e dienumerazione

! Un problema computazionale , consiste in

un insieme D, di istanze e in un insieme S,di soluzioni.

! Ad ogni istanza I # D,, è associato un

insieme S,(I) ( S, di soluzioni.

55

Problemi di ottimizzazione e dienumerazione

Dati I # D, e un insieme S ( S,(I):

! la versione decisionale ,d di , consiste nelchiedersi se S è vuoto oppure no;

! la versione di ottimizzazione (o di ricerca) ,o di ,consiste nel determinare un elemento di S;

! la versione di enumerazione (o di conteggio) ,e di, consiste nel determinare la cardinalità di S.

56

Esempio

! Per il TSP, ogni istanza I è espressa dalla

matrice delle distanze DI # DTSP, mentre le

soluzioni corrispondenti sono espresse dai

percorsi PI # STSP.

57

Esempio

Data la matrice DI # DTSP:! TSPd consiste nel chiedersi se l'insieme S ( PI che

contiene i percorsi di lunghezza minore o uguale aB è vuoto oppure no;

! TSPo consiste nel determinare un elementodell'insieme S ( PI che contiene i percorsi dilunghezza minima;

! TSPe consiste nel determinare la cardinalitàdell'insieme S ( PI.

58

Problemi di ottimizzazione NP-hard

! Le versioni di ottimizzazione dei problemi decisionali

NP-completi sono almeno difficili quanto questi

ultimi:

! calcolando una soluzione (per il TSPo un percorso di

lunghezza minima), si indica anche se un certo

sottoinsieme di soluzioni (per il TSPe, l'insieme dei percorsi

di lunghezza non superiore a B) è vuoto oppure no.

! Si dice che il problema di ottimizzazione è NP-hard.

59

Problemi di enumerazione

! Per opportune scelte dell'insieme S, le versioni di

enumerazione dei problemi decisionali NP-completi sono

almeno difficili quanto questi ultimi, e quindi NP-hard.

! Alcuni problemi di enumerazione sono candidati

all'intrattabilità, anche se P = NP.

! Esistono problemi per i quali dire se l'insieme delle

soluzioni è vuoto oppure no è “facile”, mentre contare il

numero di soluzioni risulta “estremamente difficile”!

60

La classe #P

La classe #P contiene i problemi di

enumerazione ,e che possono essere risolti

in tempo polinomiale su una MdTN.

61

La risorsa SPAZIO

! In una MdT lo spazio corrisponde in modonaturale al numero di celle di nastro chevengono utilizzate durante lacomputazione.

! Considerando le celle che servono perrappresentare l'input, lo spazio è almenopari alla lunghezza dell'input stesso.

62

La risorsa spazio

Per confrontare l'uso che diverse

computazioni fanno della risorsa spazio è

importante analizzare e quantificare lo

spazio addizionale utilizzato dalla MdT per

memorizzare i dati intermedi necessari per

procedere nella computazione.

63

La risorsa spazio

! Esistono importanti classi di problemi chepossono essere risolti usando una quantitàdi spazio addizionale molto inferiore allalunghezza dell'input.

! Per questi problemi è fondamentaledistinguere tra le attività di letturadell'input e di uso della risorsa spaziodurante la computazione.

64

MdT off-line

! La valutazione della complessità inspazio viene quindi eseguita sullaMdT off-line.

! Si tratta di una MdT con 3 nastri:! nastro di scrittura;

! nastro di lettura;

! nastro di lavoro.

65

MdT off-line

66

MdT off-line

! L'input viene letto dal nastro di solalettura o nastro di input (su cui non èconsentito scrivere);

! sul nastro di scrittura (o nastro di output)è possibile solo scrivere;

! infine, i risultati intermedi prodotti durantela computazione possono essere letti/scrittidal/sul nastro di lavoro.

67

Spazio sulla MdT off-line

Lo spazio è misurato in termini del

massimo numero di celle del nastro di

lavoro usate durante la computazione.

68

Le classi LOGSPACE e PSPACE

PSPACEclasse di linguaggi riconosciuti da una MdT che utilizzaspazio polinomiale;

POLYLOGSPACEclasse di linguaggi riconosciuti da una MdT che utilizzaspazio polilogaritmico (polinomiale nel logaritmo);

LOGSPACEclasse di linguaggi riconosciuti da una MdT che utilizzaspazio logaritmico.

69

Osservazione

Nella definizione delle ultime due classi è

cruciale fare riferimento al modello off-

line, in quanto la quantità di spazio a

disposizione è inferiore allo spazio

necessario per rappresentare l'input.

70

Inclusioni proprie tra le classi

LOGSPACE . POLYLOGSPACE . PSPACE

71

Relazioni tra spazio e tempo

! Sia , un problema risolvibile in tempo T su

una MdT.

! Lo spazio S sufficiente per risolvere ,

soddisfa S ! T:

! una computazione di T passi non può visitare

più di T celle di nastro.

72

Relazioni tra spazio e tempo

! Una macchina che opera con il limite superiore di Tunità di tempo, può vedersi ristretto lo spaziodisponibile a T unità, senza che questo ne limitiulteriormente la potenza.

! Si può dimostrare un risultato più forte:

S ! T / log T

73

Classi in spazio e in tempo

! Dalle osservazioni precedenti e dal fattoche computazioni in spazio logaritmicopossono generare al più un numeropolinomiale di descrizioni istantanee:

LOGSPACE ( P ( PSPACE.

74

Classi in spazio e in tempo

Queste inclusioni, insieme aLOGSPACE % PSPACE,

forniscono un debole risultato di separazione:! Almeno una delle due inclusioni

LOGSPACE ( P P ( PSPACEdeve essere propria.

! Non può quindi essere simultaneamenteLOGSPACE = P P = PSPACE.

75

Spazio non deterministico

Classe di Complessità NSPAZIO(f)

Insieme dei linguaggi riconosciuti da una

MdTN che utilizza, su ogni input x di

dimensione n al più f(n) celle di nastro.

76

La classe NPSPACE

La classe

NPSPACE = 'i"0 NSPAZIO(ni)

è l'analogo non deterministico della classe

PSPACE:

esprime l'imposizione di un vincolopolinomiale di spazio alla MdTN.

77

PSPACE e NPSPACE

Il confronto tra spazio polinomiale deterministico

e non deterministico è stato eseguito con

successo:PSPACE = NPSPACE

Il non determinismo non aggiunge potenza alle

macchine di Turing con un limite polinomiale allo

spazio.

78

Riusabilità dello spazio

! Grazie alla riusabilità dello spazio, una

macchina non deterministica che dispone di

spazio polinomiale non è molto più potente di

una corrispondente macchina deterministica.

! L'efficacia del non determinismo sembra

maggiore per computazioni limitate nel tempo

piuttosto che per computazioni limitate nello

spazio.

79

Inclusioni tra classi

LOGSPACE ( P ( NP ( PH ( PSPACE