Reductibilitate - Nedecidabilitate

Reductibilitate - Nedecidabilitate

1. Functii calculabile; reductibilitatea functionala
2. Problema opririi
3. Alte probleme nedecidabile in teoria limbajelor formale

Functii calculabile; reductibilitatea functionala

Definitia 1

Reducerea = o metoda de a transforma o problema P1 intr-o alta problema P2 astfel incat o solutie data problemei P2 poate fi utilizata pentru a rezolva problema P1.

Exemplul 1

P1: rezolvarea unui sistem de n ecuatii lineare cu m necunoscute, n,m I N.

P2: inversarea unei matrice.

P3: calcularea valorii unui determinant.

• Reductibilitatea functionala.
• Gasirea unei functii calculabile - numite REDUCERE - care sa transforme fiecare instanta a problemei A intr-o instanta a problemei B.

Definitie 2

Functia f : S S* se numeste calculabila

MIMT a.i. wIS*: M se opreste, avand pe banda secventa f(w) IS

Exemplul 2

Toate functiile aritmetice definite pe N sunt calculabile.

Fie f: NxN N, f(n,m)=n+m

=>construim urmatoarea MT

S=(, , , q₀, d, ) unde d

S = "Fie secventa de intrare <n,m>, n,mIN:

1. Se testeaza corectitudinea codificarii ca o secventa de n+1 simboluri 1 si m+1 simboluri 1 separate printr-un singur #. Daca exista pe banda si alte simboluri inafara de 1, # si ┴ sau daca exista mai mult decat un # atunci S respinge.

2. Se scaneaza secventa pana la intalnirea simbolului #.

3. Se inlocuieste simbolul # cu 1.

4. Se scaneaza banda pana la intalnirea primului simbol ┴.

5. Se inlocuiesc ultimele 2 simboluri 1 din extremitatea stanga cu ┴.

6. S furnizeaza rezultatul corect: n+m simboluri de 1 si se opreste.

Definitia 3

Fie limbajele A, B S*.

Limbajul A se numeste reductibil functional la limbajul B

f : S S* calculabila astfel incat ( ) wIS

wIA f(w)IB.

Functia f se numeste reducerea lui A la B.

Notatie

A _m B

Observatia 1

i) A _m B ⌐A _m ⌐B

ii) A _m B: wIA ~~> f(w)IB

=> ? wIA ~~>_f w ~ f(w) ~~>f(w)IB

Observatia 2

Reductibilitatea joaca un rol important in

(i) teoria calculabilitatii:

daca P1 este reductibila la P2 si P2 este algoritmic rezolvabila, atunci P1 este algoritmic rezolvabila;

daca P1 este reductibila la P2 si P1 este nerezolvabila algoritmic, atunci si P2 este nerezolvabila algoritmic;

(ii) teoria complexitatii:

daca P1 este reductibila la P2 atunci rezolvarea lui P1 nu poate fi mai dificila decat rezolvarea lui P2 pentru ca o solutie obtinuta pentru P2 furnizeaza o solutie pentru P1

P1 are aceeasi complexitate ca si P2.

Teorema 1

Fie limbajele A, B S*.

Daca A _m B si B = decidabil => A = decidabil.

demonstratie

Cf.ip.: "B = limbaj decidabil" T MIMT decidenta pentru B.

Cf.ip.: "A _m B " T f : S S* o reducere a lui A la B

T putem construi o MT N decidenta pentru A astfel:

N = "Fie cuvant de intrare w I S

1. Se calculeaza f(w).

2. Se ruleaza M pe intrarea f(w); rezultatul furnizat de M este preluat de N."

Evident, wIA f(w)IB T M accepta f(w) exact atunci cand wIA

M decide B N este corect definita si decide A.

Corolar 1

Fie limbajele A,B S*.

Daca A _m B si

A = nedecidabil

=> B = nedecidabil.

Corolar 2

Fie 2 limbaje A,B S

A _m B si B = Turing recunsocut

=> A = Turing recunoscut.

demonstratie

Acelasi rationament ca pt. Teorema 1, doar ca cele 2 MT, M si N, nu decid ci doar recunosc limbajele B si A.

Corolar 3

Fie 2 limbaje A,B S*: A _m B si

A Turing recunsocut

=> B Turing recunoscut.

Problema opririi

ACC_MT= = nedecidabil

HALT_MT= = nedecidabil

Vom aplica metoda reducerii:

stim ca problema acceptabilitatii pt MT este algoritmic nerezolvabila (i.e. limbajul ACC_MT este nedecidabil);

reducem problema acceptabilitatii la problema opririi

demonstram astfel ca problema opririi este si ea algoritmic nerezolvabila (i.e. limbajul HALT_MT este nedecidabil)

Teorema 2

Limbajul

HALT_MT =

este nedecidabil.

ideea demonstratiei

ppa: limbajul HALT_MT este decidabil si demonstram ca limbajul ACC_MT este decidabil, ceea ce contrazice teorema anterioara.

HALT_MT decidabil => HIMT care decide asupra limbajului HALT_MT

construim AIMT care sa decida asupra limbajului ACC_MT astfel:

A utilizeaza H pentru a "observa" comportamentul MIMT pe intrarea wIS (unde M si w sunt arbitrare), si anume:

H indica faptul ca M se opreste si accepta w

A accepta <M,w>;

H indica faptul ca M se opreste si respinge w

A respinge <M,w>;

H indica faptul ca M cicleaza pe intrarea w

convenim ca A sa respinga intrarea <M,w>

T A este decidenta nu doar acceptoare.

demonstratie

(i) Formal, AIMT este definita astfel:

A = "Fie secventa de intrare <M,w>, unde MIMT si wIS oarecare:

1. Se ruleaza MT H pe intrarea <M,w>.

2. Daca H respinge <M,w> atunci si A respinge <M,w>.

3. Daca H accepta <M,w> atunci se simuleaza M pe intrarea w pana cand M se opreste

4. Daca M accepta / respinge wIS atunci A accepta / respinge <M,w>."

(ii) Demonstram acum ca ACC_{MT m} HALT_MT

gasim o functie f : S S*, calculabila, a.i.

<M,w>: <M,w>IACC_MT f(<M,w>) = <M',w'>IHALT_MT.

Fie urmatoarea MT , F, care calculeaza o astfel de reducere f:

F = "Fie secventa de intrare <M,w>, unde MIMT si wIS

1. Se construieste urmatoarea MT M' astfel:

M' = "Fie cuvantul de intrare x I S

2. Se ruleaza M pe intrarea x.

3. Daca M accepta x, atunci si M' accepta x.

4. Daca M respinge x, atunci M' cicleaza."

5. Se returneaza secventa <M',w>."

Cf. presupunerii prin absurd: H este decidenta si decide asupra limbajului HALT_MT ;

Conform (i), (ii) si Teoremei 1: AIMT este si ea decidenta si decide asupra limbajului ACC_MT.

Dar, conform teoremei ant., limbajul ACC_MT nu este decidabil

T contradictie

T limbajul HALT_MT este nedecidabil.

Alte probleme nedecidabile in teoria limbajelor formale

Teorema 3

Limbajul

EMP_MT =

este nedecidabil.

demonstratie

M'="Fie secventa de intrare xIa*, oarecare:

1. Daca x w, atunci M' respinge.

2. Daca x=w, atunci se ruleaza M pe intrarea w.

3. Daca M accepta w, atunci M' accepta x"

Ppa ca avem EIMT care decide asupra limbajului EMP_MT. Construim A pt ACC_MT:

A ="Fie secv. de intrare <M,w>, MIMT, wIa*, oarecare:

1. Se construieste, cu ajutorul descrierii <M,w>, o MT M' cf. definitiei de mai sus.

2. Se ruleaza E pe intrarea <M'>.

3. Daca E accepta <M'>, atunci A respinge <M,w> iar daca E respinge <M'> atunci A accepta <M,w>."

Cf. ip. noastre: E=decidenta si cf. def. A de mai sus: => A decidenta

=> lb. ACC_MT decidabil => (cf. teorema ant.) contradictie

=> lb. EMP_MT= nedecidabil.

Teorema 4

Limbajul

EQ_MT =

este nedecidabil.

demonstratie

ppa: FIMT, decidenta, pt limbajul EQ_MT;

construim EIMT, care sa decida asupra limbajului EMP_MT:

E = "Fie secventa de intrare <M>, MIMT:

1. Se ruleaza F pe intrarea <M,M₁>, unde M₁ este o MT care respinge toate intrarile primite.

2. Daca F accepta <M,M₁>, atunci E accepta <M>; daca F respinge, atunci E respinge."

Demonstram ca EMP_{MT m} EQ_MT

gasim o functie g : S S*, calculabila, a.i.

wIS*, w=<M>IEMP_MT g(<M>) = <M',M₁>IEQ_MT, unde M', M₁IMT sunt ca mai sus.

Fie urmatoarea MT , G, care calculeaza o astfel de reducere g:

G = "Fie secventa de intrare <M>, unde MIMT:

1. Se construieste M'IMT astfel:

M' = "Fie cuvantul de intrare wIS

2. Se ruleaza M pe intrarea w.

3. Daca M respinge w, atunci si M' respinge w.

4. Daca M accepta w, atunci M' cicleaza."

5. Se returneaza secventa <M',M₁>, unde M₁IMT si L(M₁)=

Cf. def. lb. EQ_MT si constructiei propuse:

daca F accepta <M,M₁> L(M)=L(M1) L(M)= E accepta <M>;

daca F respinge <M,M₁> L(M) L(M1) L(M) E respinge <M>.

Cf. pp. noastre: F=decidenta => E=decidenta (cf. constructiei de mai sus).

=> EMP_MT=decidabil => contradictie => EQ_MT=nedecidabil.

Observatia 3

? B S*: B Turing-recunoscut.

daca aratam ca ACC_{MT m} ⌐B

⌐ACC_{MT m} B                              (*)

Teorema ant.: ⌐ACC_MT Turing-recunoscut                         (**)

(*) + (**) + Corolar 2 => B Turing-recunoscut

=> pt a demonstra ca un limbaj B NU este Turing-recunoscut este suficient sa demonstram ca ACC_{MT m} ⌐ B.

Corolarul 4

Limbajul

EQ_MT =

nu este nici Turing-recunoscut nici co-Turing-recunoscut.

demonstratie

(i) EQ_MT nu este Turing-recunoscut

e suficient sa demonstram ca ACC_{MT m} ⌐ EQ_MT.

Urmatoarea MT, F, calculeaza aceasta reducere f:

F = "Fie secventa de intrare <M,w>, unde MIMT si wIS

1. Se construiesc urmatoarele 2 MT: M₁ si M₂:

M₁ = "Oricare ar fi secventa de intrare xIS

2. M₁ respinge x."

M₂ = "Oricare ar fi secventa de intrare xIS

3. Se ruleaza M pe intrarea w.

4. Daca M accepta w atunci M₂ accepta x."

5. F produce la iesire secventa <M₁,M₂>."

f este corect definita:

(1) M₁ nu accepta nimic;

(2) daca M accepta w M₂ accepta orice

M nu accepta w M₂ nu accepta nimic;

din (1) +(2) =>

daca <M,w>IACC_MT M₂ M₁,

<M,w> ACC_MT M₂=M₁

=> f reduce ACC_MT la ⌐ EQ_MT^.

(ii) ⌐ EQ_MT nu este Turing-recunoscut

analog, dem. ca ACC_{MT m} ⌐ (⌐ EQ_MT), adica ACC_{MT m}EQ_MT

Urmatoarea MT, G, calculeaza aceasta reducere g:

G = "Fie secventa de intrare <M,w>, unde MIMT si wIS

1. Se construiesc urmatoarele 2 MT: M₁ si M₂:

M₁ = "Oricare ar fi secventa de intrare xIS

2. M₁ accepta x."

M₂ = "Oricare ar fi secventa de intrare xIS

3. Se ruleaza M pe intrarea w.

4. Daca M accepta w atunci M₂ accepta x."

5. G produce la iesire secventa <M₁,M₂>."

g este corect definita:

(1) M₁ accepta orice intrare;

(2) daca M accepta w M₂ accepta orice

M nu accepta w M₂ nu accepta nimic;

din (1) +(2) =>

daca <M,w>IACC_MT M₂=M₁,

<M,w> ACC_MT M₂ M₁

=> g reduce ACC_MT la EQ_MT^.

Din (i) si (ii) EQ_MT nu este nici Turing-recunoscut, nici co-Turing-recunoscut.

1. Masina Turing vs. alte modele de calcul
2. Automatul linear marginit
3. Problema lui POST

Masina Turing vs. alte modele de calcul

Observatia 1

O MT poate sa recunoasca un limbaj care poate fi recunoscut si de un model de calculabilitate mai slab: un automat finit, un automat pushdown etc. ?

De exemplu, poate o MT sa recunoasca un limbaj regulat ?

Teorema 1

Limbajul

REG_MT =

este nedecidabil.

demonstratie

Ppa. RIMT care decide asupra REG_MT

Construim, cu ajutorul R, o MT A care sa decida asupra limbajului ACC_MT :

A = "Fie secventa de intrare <M,w>, unde MIMT si wIS

1. Se construieste urmatoarea M₂IMT :

M₂ = "Fie secventa de intrare xIS

1. Daca x este de forma 0ⁿ1ⁿ atunci M₂ accepta x.

2. Altfel, se ruleaza M pe intrarea w si, daca M accepta w atunci M₂ accepta x."

2. Se ruleaza R pe intrarea <M₂>.

3. Daca R accepta /respinge <M₂> atunci A accepta / respinge <M,w>.

Fie P o proprietate oarecare netriviala a lb. r.e.

=> problema verificarii faptului ca limbajul recunoscut de o MT data poseda proprietatea P NU este rezolvabila algoritmic.

Teorema lui Rice

Fie limbajul P = .

Presupunem ca limbajul P satisface urmatoarele doua proprietati:

(i) P nu este trivial

(adica: propr. avuta in vedere are loc pentru unele limbaje r.e. iar pentru altele nu are loc,

sau inca: ( ) M₁,M₂IMT astfel incat <M₁> I P si <M₂> P)

(ii) P este o proprietate a limbajelor recunoscute de MT

(adica: aparteneta unei MT M la P (prin descrierea ei <M>) depinde numai de limbajul recunoscut de M,

sau inca: M₁ M₂IMT cu proprietatea L(M₁) = L(M₂) atunci <M₁> I P <M₂> I P).

Atunci, limbajul P este nedecidabil.

demonstratie

Analog: ppa limbajul P avand cele 2 proprietati este decidabil

=> R_PIMT care decide asupra limbajului P.

Construim cu ajutorul lui R_P o alta MT, A, care sa decida asupra ACC_MT.

Pt aceasta: fie R IMT care respinge orice cuvant,

Putem pp ca < R > P.

Cf. ip (i): cel putin o MT, R, a.i. <R>IP.

=> putem construi A folosind capacitatea MT R_P de a distinge intre MT R si R

A = "Fie secventa de intrare <M,w>, unde MIMT si wIS

1. Se construieste MT M_w, cu ajutorul descrierii lui M si w::

M_w = "Fie secventa de intrare xIS

2. Se simuleaza M pe intrarea w.

Daca M se opreste si respinge w, atunci M_w respinge x;

daca M accepta w, atunci se trece la Pasul 4.

3. Se simuleaza R pe intrarea x.

Daca R accepta x atunci M_w accepta x."

4. Se utilizeaza MT R_P pt a determina daca < M_w>IP.

Daca da, atunci A accepta <M,w>, altfel respinge."

Definitia MT, A MT, M_w simuleaza R daca M accepta w, adica:

Am convenit ca <R>IP => (cf (ii)) <M_w>IP => (def.A) M accepta w => <M,w>IACC_MT.

=> contradictie.

Automatul linear marginit

Definitia 1

Un automat linear marginit (ALM) este un tip restrictionat de MT in care cursorul nu se poate deplasa pe banda de lucru inafara zonei care contine secventa de intrare.

Daca functia de tranzitie a MT impune deplasarea cursorului dincolo de oricare dintre cele 2 capete ale secventei de intrare, atunci acesta este fortat sa ramana pe loc.

Observatia 2

a) Un ALM = o MT cu memorie limitata

=> poate rezolva numai probleme care necesita un spatiu de memorie egal cu cel necesar memorarii secventei de intrare.

b) G S spatiul de memorie disponibil pt ALM creste cu un factor constant

=>spunem ca spatiul de memorie creste linear cu dimensiunea intrarii.

c) ALM: memorie limitata dar putere de calcul mare:

MT pentru ACC_AFD, ACC_GIC, EMP_AFD, EMP_GIC sunt ALM.

d) ACC_ALM este identica cu problema nedecidabila ACC_MT dar este decidabila.

Definitia 2

Configuratie a unei MIMT = un triplet format din:

• starea curenta a M, q;
• continutul curent al benzii, v^.w ;
• pozitia curenta a cursorului.

Notatie

vqw, v,wIG*, qIQ.

Exemplul 1

Configuratia 1011q₇01111 inseamna:

Eseu: Sistemul periodic al elementelor Referat: Repartitia unei substante intre doi solventi nemiscibili (Legea de distributie a lui Nernst)

Definitia 3

Configuratia C₁ produce configuratia C₂

MT trece - corect - din C₁ in C₂ intr-un singur pas

Fie a,b,c I G

v,w I G

q_i, q_j I Q

Spunem ca o configuratie C₁=vaq_ibw produce

• configuratia C₂=vq_jacw daca d(q_i,b)=(q_j,c,L);
• configuratia C₂=vacq_jw daca d(q_i,b)=(q_j,c,R).

Lema 1

Fie MIALM: |Q|=q, |a|=s

=> numarul de configuratii distincte ale M pentru o banda de lucru de lungime n este

q^.n^.sⁿ.

demonstratie

O configuratie este un pas de calcul efectuat de M pe intrarea primita;

ea consta din starea controlului, pozitia cursorului si continutul benzii.

cf. ip.:  M poate fi in una dintre cele q stari,

lungimea benzii este n,

secventele citite sunt compuse din s simboluri

=> pe banda se pot afla sⁿ secvente distincte

=> numarul total de configuratii este dat de produsul celor 3 factori

q^.n^.sⁿ.

Teorema 2

Limbajul

ACC_ALM =

este decidabil.

demonstratie

L = "Fie secventa de intrare <M,w>, unde MIALM si wIS

1. Se simuleaza M pe intrarea w timp de q^.n^.sⁿ pasi sau pana ce M se opreste.

2. Daca M s-a oprit, atunci: daca M a acceptat, L accepta iar daca M a respins, L respinge.

3. Daca M nu s-a oprit atunci L respinge."

Observatia 3

MT si ALM difera in mod esential: ACC_ALM= decidabil dar ACC_MT=nedecidabil.

Totusi, alte probleme raman nedecidabile si pt ALM.

Metoda istoricului calculului

• reductibilitatea PROBLEMEI ACCEPTABILITATII pt MT, ACC_MT, la anumite limbaje
• testarea existentei unui obiect sau a unei proprietati.

Exemplul 2

Problema a 10-a a lui Hilbert: existenta radacinilor intregi pentru p, p=polinom.

Istoricul unui calcul efectuat de o MT pe o secventa de intrare data =

sirul de configuratii prin care respectiva MT trece atunci cand proceseaza intrarea respectiva.

Definitia 4

Fie MIMT si wIa

Istoricul unui calcul de acceptare efectuat de M pe w este o secventa de configuratii C₁,C₂, . ,C_f, unde:

• C₁ este configuratia de start a lui M pentru w,
• C_f este o configuratie finala de acceptare a lui M si
• i f: C_i se obtine corect din C_i-1 prin aplicarea regulilor de tranzitie ale M.

Istoricul unui calcul de respingere: C_f este o configuratie finala de respingere a lui M

Observatia 4

Secventa de configuratii: FINITA

Teorema 3

Limbajul

EMP_ALM =

este nedecidabil.

ideea demonstratiei

Folosim metoda reducerii la absurd si reductibilitatea de la problema acceptabilitatii

Fie MIMT si w=w₁w₂ . w_nIS ; construim un BIALM astfel:

• L(B) consta din toate istoricele calculelor de acceptare efectuate de M asupra w
• daca M accepta w atunci limbajul L(B) consta dintr-o singura secventa daca M nu accepta w, atunci L(B)=

=> Daca am putea determina daca L(B)= am putea determina daca M accepta w si am obtine contradictia cautata.

Fie MIMT si wIS ; vom demonstra existenta BIALM si vom descrie modul in care o MT poate obtine o descriere a lui B pornind de la descrierile lui M si w

B accepta secventa de intrare x x este un istoric al unui calcul de acceptare al M pe w.

=>presupunem ca un istoric al unui calcul de acceptare se prezinta sub forma unei secvente unice

Modul de lucru al BIALM

1) B primeste secventa de intrare x;

2) B verifica daca x reprezinta un istoric al unui calcul de acceptare al M pe w:

B divizeaza secventa x in secventele C₁, C₂, . ,C_f, in conformitate cu delimitatorii #;

B verifica daca acestea satisfac cele 3 conditii din definitia unui istoric de calcul:

C₁ este configuratia de start a lui M pe w:

dar C₁=q₀w₁w₂ . w_n; aceasta informatie este cuprinsa in chiar descrierea <M,w> => B o poate verifica direct; 

C_f=configuratie finala de acceptare a lui M pe w:

dar C_f trebuie sa contina starea q_a => B trebuie sa scaneze secventa C_f pt a determina prezenta lui q_a;

pentru fiecare pereche de configuratii adiacente, B verifica daca C_i+1 provine, corect, din C_i:

Aceasta verificare presupune:

testarea faptului ca C_i si C_i+1 sunt identice, cu exceptia locatiilor din C_i aflate sub cursor adiacente acestuia;

actualizarea acestor locatii cf. functiei de tranzitie a lui M;

executarea unei miscari de "du-te vino" intre locatiile care se corespund din C_i si C_i+1, pentru a verifica daca actualizarea s-a facut corect;

punctarea simbolului din locatia curent verificata, pentru a tine evidenta pozitiei curente a cursorului in cele 2 configuratii in timpul acestei pendulari.

3) Daca cele 3 conditii sunt satisfacute, B incheie prin a accepta intrarea primita.

demonstratie

Fie RIMT care decide asupra limbajului EMP_ALM;

Definim SIMT care decide asupra limbajului ACC_MT astfel:

S = "Fie secventa de intrare <M,w>, unde MIMT, wIS*:

1. Se construieste BIALM pe baza descrierilor lui M si w, conform indicatiilor de mai sus.

2. Se ruleaza R pe intrarea <B>.

3. Daca R respinge, atunci S accepta; daca R accepta, atunci S respinge."

Observatie

R accepta <B> L(B)= M nu are niciun istoric de calcul de acceptare pt. w M nu accepta w => S respinge <M,w>.

R respinge <B> L(B) : singura secventa pe care o poate accepta B este un istoric de calcul de acceptare al M pt w M trebuie sa accepte w => S accepta <M,w>.

Teorema 4

Limbajul

ALL_GIC =

este nedecidabil.

ideea demonstratiei

Folosim metoda reducerii la absurd si reductibilitatea de la problema acceptabilitatii precum si tehnica istoricului calculului efectuat pt un cuvant.

Fie MIMT si wIS*, oarecare: sa pp ca reprezentam un istoric al calculului de acceptare al M pe w prin #C₁#C₂##C_f#, unde C_i este configuratia lui M la pasul i din calculul lui w.

construim o GIGIC care genereaza toate cuvintele din S

M nu accepta w.

Daca M accepta w (cf. def. G de mai sus) xIS*: x L(G); acest cuvint este tocmai istoricul calculului de acceptare al M pe w.

=> G este construita astfel incat sa genereze toate cuvintele care nu sunt istorice ale calculelor de acceptare ale M pe w.

Observatii

1) xIS* nu poate fi un istoric de calcul de acceptare

nu indeplineste cel putin una dintre cele 3 conditii din Definitia 2, adica: (1') nu incepe cu C1;

(2') nu se termina cu o configuratie finala de acceptare;

(3') i f-1: configuratia C_i nu produce corect, in conformitate cu regulile de tranzitie din M, configuratia C_i+1.

2) in loc sa construim o GIGIC vom construi un DIAPD deoarece exista o procedura algoritmica de convertire a unui APD intr-o GIC si un APD este - in cazul nostru - mai usor de construit.

Astfel, D va incepe prin " a ghici" nedeterminist pe care dintre cele 3 reguli sa le verifice; => in arborele de derivare va exista un nod din care pornesc 3 ramuri de calcul:

• pe prima ramura se verifica daca secventa de intrare incepe cu configuratia initiala, C₁ si accepta in cazul negativ;
• pe a 2a ramura se verifica daca secventa de intrare se incheie cu configuratia finala de accepatre, C_f si accepta in cazul negativ (verificarea revine la identificarea prezentei lui q_a in C_f);
• pe a 3a ramura se verifica daca exista vreo configuratie C_i care nu produce corect configuratia adiacenta C_i+1. Se procedeaza astfel:

- D scaneaza intrarea #C₁#C₂##C_f# pana decide in mod nedeterminist ca a ajuns la configuratia C_i;

- D introduce C_i in stiva, pana la delimitatorul #;

- D extrage din stiva pt a face comparatia cu C_i+1; cele 2 secvente ar trebui sa coincida, mai putin in dreptul si in jurul cursorului unde relatia dintre ele ar trebui sa respecte definitia functiei de tranzitie a lui M;

- D ar trebui sa accepte daca exista o nepotrivire intre configuratii sau daca actualizarea nu a respectat definitia lui d_M

Problema prezenta in aceasta strategie este ca extragerea C_i din stiva se face in ordinea inversa introducerii, ceea ce impiedica compararea ei cu C_i+1.

Pt a evita aceasta dificultate, vom reprezenta de la bun inceput secventa de intrare formata din sirul de configuratii C₁,C₂,,C_f, astfel:

=> acum D poate introduce in stiva configuratia a.i. atunci cand o extrage sa o poata compara cu configuratia urmatoare.

Proiectam DIAPD a.i. sa accepte orice secventa care nu este un istoric de calcul de acceptare in forma modificata de mai sus.

Problema corespondentei lui Post

Definim o multime de dominouri astfel:

Putem intotdeauna forma o secventa din dominourile din multime a.i. "secventa numaratorilor" sa coincida cu "secventa numitorilor" (i.e. intotdeauna o "coincidenta"?)

Exemplu:

Contraexemplu:

=> Problema corespondentei lui Post (PCP) revine la a determina, pentru orice multime de dominouri, daca prezinta o coincidenta sau nu.

Formalizam PCP astfel:

• o instanta a PCP este o colectie P de dominouri definita prin:

• o coincidenta este o secventa de indici i₁,i₂, . ,i_k astfel incat:

• PCP consta in a determina daca o colectie oarecare de dominouri P prezinta o coincidenta.

Teorema 5

Limbajul

.

este nedecidabil.

Complexitatea modelelor de calcul

1. Terminologie
2. Notatia asimptotica
3. Analiza algoritmilor
4. Complexitatea modelelor de calcul

Terminologie

Problema rezolvabila algoritmic in principiu

Problema nerezolvabila algoritmic in practica

Timpul de calcul

Spatiul de memorie

Fie limbajul

L_k = ;

L_k ILIC si

ACC_LIC este decidabil

=> L_k = decidabil.

Problema care ne intereseaza acum este insa:

"dupa cat timp o MT raspunde afirmativ la aceasta intrebare?"

(I) Fie M₁IMT, o MT clasica care calculeaza L_k.

M₁ = "Fie cuvantul de intrare wIS

1. Se examineaza banda de intrare si se respinge w daca se descopera un simbol 0 la dreapta unui simbol 1.

2. Se executa etapa urmatoare, atat timp cat pe banda exista atat simboluri 0 cat si simboluri 1:

3. Se scaneaza banda si se bareaza un singur simbol 0 si un singur simbol 1.

4. Daca, dupa ce toate simbolurile 0 au fost barate pe banda au mai ramas simboluri 1 nebarate, sau daca, dupa ce toate simbolurile 1 au fost barate pe banda au mai ramas simboluri 0 nebarate, atunci M₁ respinge w.

Altfel, daca toate simbolurile 0 si toate simbolurile 1 de pe banda au fost barate, atunci M₁ accepta secventa w."

Numarul de pasi executati de un algoritm poate depinde de mai multi parametri.

Exemplu: data de intrare este un graf

numarul de pasi: numarul de noduri / muchii, de gradul maxim al grafului, de o combinatie a acestor factori si / sau a altora.

Aici, TIMPUL DE EXECUTIE: functie de LUNGIMEA SECVENTEI

Se pot aborda:

• cazul cel mai nefavorabil
• cazul cel mai favorabil
• cazul mediu

Notatia asimptotica

Definitie 1

Fie M o MT determinista cu 1! banda, decidenta,

wIS* un cuvant de intrare,

C₀C₁C₂ . C_dC_f. cele d+2, d 0, configuratii prin care trece M pentru a prelucra cuvantul w;

Complexitatea timp a M pe intrarea w este numarul intreg notat

TIME_M(w) = d+1

Definitie 2

Fie M o MT determinista cu 1! banda decidenta.

Complexitatea timp s timpul de executie al M este o functie

f : N N, definita prin:

f(n) = numarul maxim de pasi executati de M pentru o secventa de intrare de lungime n, nIN .

Notatia 1

f(n) = max = TIME_M(n)

Exemplul 1

Fie f : N N, f(n) = 5n³ + 2n² + 22n + 6;

spunem ca f tinde asimptotic catre n³ si notam acest lucru cu O(n³)

Definitie 3

Fie f, g : N R₊

(i) f(n) = O(g(n)) si citim "f(n) este de ordin cel mult g(n)" sau "f(n) este O mare de g(n)"

( ) constantele c₁ > 0 si n₁ I N astfel incat f(n) c₁.g(n), ( ) n n₁.

(ii) f(n) = W (g(n)) si citim "f(n) este de ordin cel putin g(n)" sau "f(n) este omega mare de g(n)"

( ) constantele c₂ > 0 si n₂ I N astfel incat f(n) c₂.g(n), ( ) n n₂.

(iii) f(n) = Q (g(n)) si citim "f(n) este de ordin g(n)" sau "f(n) este theta de g(n)"

f(n) = O(g(n)) si f(n) = W (g(n)).

Spunem ca g este o limita asimptotica superioara,

o limita asimptotica inferioara, respectiv

o limita asimptotica pentru f.

Exemplul 2

Revenim la notatia O si la functia polinomiala

f(n) = 5n³ + 2n² + 22n + 6 T

f(n) = O(n³), de exemplu, pentru c₁ = 6 si n₁ = 10;

f(n) = O(n⁴), de exemplu, pentru c₁ = 1 si n₁ = 6 sau

pentru c₁ = 36 si n₁ = 1;

f(n) O (n²),

presupunem prin absurd ca exista c₁ > 0 si n₁ I N astfel incat

5n³ + 2n² + 22n + 6 c₁.n₂, ( ) n n₁

5n³ + (2- c₁).n² + 22n + 6 0 etc.

Exemplul 3

Fie f₁ : N N, f₁(n) = 3n.log₂n + 5n.log₂(log₂n) + 2 T

f₁(n) = O(n.log n) pentru ca log n domina log(log n).

Analog, f₂(n) = O(n²) + O(n) f₂(n) = O(n²)

pentru ca O(n²) domina O(n).

Observatia 1

A)    Specificarea bazei logaritmilor nu este necesara ea intervenind cu cel mult un coeficient constant, conform formulei:

B)     Analog, nici specificarea bazei exponentialei nu este necesara pentru ca:

2^{O(log n)} este o limita superioara pentru n^c, unde c este o constanta oarecare. Evident, si 2^O(n) este o limita superioara pentru n^c.

Observatia 2

Limitele asimptotice de tipul n^c se numesc limite polinomiale.

Limitele asimptotice de tipul se numesc limite exponentiale.

Limitele asimptotice de tipul k.n se numesc limite lineare.

Limitele asimptotice de tipul se numesc limite sublineare.

Observatia 3

Pe langa notatiile O si W mai exista si notatiile o si w , obtinute din Definitia 2 prin inlocuirea inegalitatii cu inegalitatea stricta < , sau

Exemplul 4

n =o(n.log log n)

n.log log n = o(n.log n)

n.log n = o (n²)

n² = o(n³)

Propozitia 1

(i) Notatiile O, W Q, o, w sunt tranzitive:

f(n) = O(g(n)) & g(n) = O(h(n)) f(n) = O(h(n)) etc.;

(ii) Notatiile O, W Q, sunt reflexive, dar nu si o, w

f(n) = O(f(n)) dar f(n) o(f(n)) etc.;

(iii) Notatia Q este simetrica dar nu si celelalte notatii:

f(n) = Q(g(n)) g(n) = Q(f(n)).

Propozitia 2

Notatiile O, W etc. pot fi manipulate algebric, dar cu precautie (de ex. egalitatea din formula (5) are loc intr-un singur sens: de la stanga la dreapta):

1. c.O(f(n)) = O(f(n));
2. O(f(n)) + O(f(m)) = O(f(n));
3. O(O(f(n))) = O(f(n));
4. O(f(n)) ^. O(g(n)) = O(f(n)^.g(n));
5. O(f(n)^.g(n)) = f(n)^.O(g(n)).

Analiza algoritmilor

L_k = .

Fie | 0^k1^k | = n.

Pentru a efectua prima etapa a algoritmului trebuie n pasi

T O(n) pasi.

Aducerea cursorului in extr. stanga pentru a incepe bararea: n pasi

T O(n) pasi.

In etapele 2, 3 MT scaneaza in mod repetat banda pentru a bara simbolurile 0 si 1.

Fiecare scanare necesita n pasi iar la fiecare scanare se bareaza 2 simboluri

T se fac n/2 scanari de cate n pasi fiecare T O(n²) pasi.

In etapa 4, MT face o singura scanare pentru a hotari daca accepta / respinge secventa de intrare

T se executa maximum n pasi T O(n) pasi.

T f(n) = O(n) + O(n) + O(n²) + O(n) = O(n²)

Definitia 4

Fie o functie t : N ® R⁺.

Se defineste clasa de complexitate timp polinomial prin:

TIME(t(n))

Exemplul 5

L_k = I TIME(n²) pentru ca:

• M₁ decide asupra L_k in timp O(n²),
• TIME(n²) contine toate limbajele asupra carora se poate decide in timp O(n²).

Putem defini o MT care sa decida asupra limbajului L_k mai repede?

(II) Modificam MT M₁ astfel incat la fiecare etapa 3 baram cate doua simboluri 0 si doua simboluri 1 T

reducem numarul de scanari din etapa 3 la jumatate T

avem n/4 scanari de cate maximum n pasi fiecare T

O(n²) T

aceasta reducere inseamna un factor constant egal cu 2

=> nu afecteaza timpul asimptotic de executie al algoritmului;

M₂ = "Fie cuvantul de intrare w I S

1. Se scaneaza banda de intrare; daca w nu este de forma 0⁺1⁺ atunci M₂ respinge.

2. Se executa urmatoarele doua etape, atat timp cat pe banda exista atat simboluri 0 cat si simboluri 1 nebarate:

3. Se scaneaza banda pentru a determina daca numarul total de simboluri 0 si 1 aflat pe banda este impar.

Daca da, atunci M₂ respinge.

4. Se scaneaza banda din nou si se bareaza fiecare al doilea simbol 0 incepand de la primul 0 si apoi fiecarea al doilea simbol 1 incepand de la primul 1.

5. Daca, dupa ce toate simbolurile 0 au fost barate pe banda au mai ramas simboluri 1 nebarate, sau daca, dupa ce toate simbolurile 1 au fost barate pe banda au mai ramas simboluri 0 nebarate, atunci secventa w se respinge.

Altfel, daca toate simbolurile 0 si toate simbolurile 1 de pe banda au fost barate, atunci secventa w se accepta."

Este evidenta similitudinea dintre masinile M₁ si M₂;

=> M₂ decide asupra limbajului L_k.

Calculam acum timpul sau de executie:

• observam ca fiecare etapa se executa in O(n) pasi;
• numaram de cate ori se executa fiecare etapa:

etapa 1: 1! data,

etapa 5: 1! data,

etapa 4: la fiecare scanare se bareaza cel putin 1/2 din numarul de simboluri 0 si 1/2 din numarul de simboluri 1 T

e nevoie de cel mult (1+log₂n) scanari pentru a bara toate simbolurile T

etapele 2,3,4 se executa de cel mult (1+log₂n) ori.

T timpul de executie pentru M₂ este de:

1.O(n) + (1+log₂n).O(n) + 1.O(n) = O(n.log n) + O(n) = O(n.log n)

T L_kITIME n.log n)

Putem micsora in continuare timpul de executie?

o(n.logn)=?

Teorema 1

Fie f : N à R⁺ cu proprietatea: f(n) = o(n.logn)

=> TIME(f(n)) =

(III) Limbajul L_k poate fi decis chiar in timp linear daca MT respectiva are doua benzi. Fie masina Turing M₃ cu doua benzi definita astfel:

M₃ = "Fie cuvantul de intrare w I S

1. Se scaneaza banda de intrare; daca exista cel putin un simbol 0 la dreapta unui simbol 1, atunci M₃ respinge.

2. Se scaneaza subsirul de simboluri 0 de pe banda 1 a MT pana la intalnirea primului simbol 1 si se copiaza pe banda 2 a MT.

3. Se scaneaza subsirul de simboluri 1 ramas pe banda 1 a MT pana la sfarsit, barandu-se - pentru fiecare simbol 1 scanat - cate un simbol 0 de pe Banda 2.

4. Daca toate simbolurile 0 de pe banda 2 au fost barate dar pe banda 1 au mai ramas simboluri 1 de citit sau daca pe banda 2 au mai ramas simboluri 0 nebarate dar pe banda 1 nu mai sunt simboluri 1 de citit, atunci M₃ respinge.

Altfel, daca toate simbolurile 0 de pe Banda 2 au fost barate iar pe banda 1 nu au mai ramas simboluri 1 de citit, atunci M₃ accepta."

Evident, M₃ decide asupra limbajului L_k;

Calculam timpul sau de executie:

fiecare etapa necesita cel mult O(n) pasi si se executa o singura data

=> timpul de executie este linear si

el nu mai poate fi imbunatatit pt ca citirea secventei de intrare necesita n pasi.

Observatie importanta

• cu o MT cu o singura banda, L_k este decidabil in timp O(n²) sau O(n.log n);
• nici o MT determinista cu o singura banda nu poate ameliora performanta de mai sus;
• cu o MT cu doua benzi, L_k este decidabil in timp O(n).

T complexitatea timp a problemei L_k poate fi ameliorata daca gasim un algoritm mai eficient (o MT mai eficienta)

T complexitatea problemei L_k depinde de modelul de calculabilitate ales.

• in teoria calculabilitatii:

Teza Church-Turing arata ca toate modelele de calculabilitate "valabile" sunt echivalente intre ele;

• in teoria complexitatii:

alegerea unui model de calculabilitate afecteaza complexitatea-timp a limbajului (problemei):

un limbaj care - intr-un model de calculabilitate - este decidabil in timp linear poate sa fie - in alt model de calculabilitate - decidabil doar in timp polinomial.

Faptul ca acelasi limbaj poate necesita timpi de calcul diferiti in diferite modele de calculabilitate pare sa torpileze orice incercare de clasificare a problemelor de calculabilitate in functie de complexitatea timp a acestora.

Necesarul de timp de calcul nu difera in mod esential la nivelul modelelor de calcul deterministe.

Complexitatea modelelor de calcul

Vom analiza trei modele de calculabilitate:

• MT cu o singura banda (clasica);
• MT cu mai multe benzi;
• MT nedeterminista.

Teorema 2

Fie t : N N o functie cu proprietatea ca nIN : t(n) n.

=> MIMT cu mai multe benzi si cu timp de lucru t(n)

SIMT, cu 1! banda de intrare si cu timp de lucru O(t²(n)): L(S)=L(M).

demonstratie

Fie MIMT cu k benzi de intrare care ruleaza in timp t(n), t : N N, t(n) n, nIN

Construim (dupa metoda utilizata anterior) o MT S cu o singura banda de intrare care sa simuleze M si analizam timpul de lucru care necesar.

Initial, S depune pe banda sa de intrare continuturile celor k benzi al M, separandu-le printr-un caracter special, #, # S_S S_M

in plus, S simuleaza pozitiile cursoarelor lui M prin bararea simbolurilor corespunzatoare de pe banda sa (inlocuieste un simbol s cu s', sI G_S G_M

Apoi, S simuleaza pasii efectuati de M pentru un cuvant de intrare oarecare, wIS*. Pentru a simula un pas efectuat de M, S:

• trebuie sa scaneze toata informatia depusa pe banda sa de intrare ca sa poata astfel determina simbolurile aflate "sub" cursoarele lui M;
• apoi, S isi parcurge din nou banda de intrare pentru a actualiza continutul acesteia si a repozitiona cursoarele virtuale, conform definitiei functiei de tranzitie a lui M, d_M.
• daca vreunul dintre cursoarele reale ale M se deplaseaza la dreapta pe propria sa banda de lucru peste o celula vida, atunci S trebuie sa-si mareasca spatiul alocat pe unica sa banda de intrare.

S face acest lucru deplasand toata informatia (aflata pe banda sa la dreapta celulei respective) cu o locatie la dreapta.

Analizam acum aceasta simulare din punctul de vedere al timpului de calcul necesar.

Pentru fiecare pas executat de M, S parcurge de 2 ori portiunea activa (cu informatie) a benzii sale de intrare:

• prima parcurgere serveste la obtinerea informatiei necesare pentru a determina miscarea urmatoare;
• a doua parcurgere serveste la efectuarea acestei miscari.

Timpul necesar efectuarii acestor parcurgeri este evident determinat de numarul celulelor cu informatie de pe banda lui S.

=> cautam deci o limita superioara pentru aceasta lungime.

Conform constructiei lui S:

Deci, S scaneaza portiunile cu informatie de pe banda sa de intrare in O(t(n)) pasi (modulo constantele k si k + 1, banda lui S este "la fel de lunga" ca oricare dintre benzile lui M).

b) Evaluam acum fiecare pas al lui S:

Pentru a simula oricare dintre pasii lui M , S efectueaza 2 scanari ale benzii sale si maximum k deplasari ale informatiei sale la dreapta.

Conform (*), fiecare dintre acesti pasi consuma:

• un timp de calcul de ordinul O(t(n)) pentru fiecare dintre cele doua scanari si
• un timp de lucru constant pentru cele maximum k deplasari la dreapta (cand cursoarele virtuale ajung peste delimitatori).

=> timpul total in care S simuleaza un pas oarecare l lui M este de ordin O(t(n)).

c) Insumam acum si gasim o limita superioara a timpului total:

In prima etapa, in care S copiaza pe banda sa informatiile de pe cele k benzi ale M si le separa prin delimitatorii #, lui S ii sunt necesari O(n) pasi deoarece, conform ipotezei, M ruleaza - pe o intrare de lungime n - in timp t(n).

Ulterior, S simuleaza fiecare dintre cei (conform ipotezei) t(n) pasi ai lui M in O(t(n)) pasi

=> aceasta parte a simularii lui M de catre S consuma.

t(n) x O(t(n)) = O(t²(n))

In total, intreaga simulare consuma

O(n) + O(t²(n)) pasi

Dar, cf. ip.: t(n) n, ( ) n I N

=> putem aprecia timpul total de executie al lui S la O(t²(n)).

Observatia 4

Ipoteza t(n) n, ( ) n I N nu este restrictiva, ci dimpotriva: in caz contrar, M "nu ar avea timp" nici macar sa citeasca toata informatia, daramite sa o prelucreze!

Definitie 5

Fie N o MT nedeterminista cu 1! banda, decidenta,

wIL(M) S

Complexitatea timp a N pe intrarea w este numarul intreg notat TIME_N(w) care reprezinta lungimea celui mai scurt calcul care accepta w, efectuat de N.

Definitie 6

Fie N o MT nedeterminista cu 1! banda, decidenta,

Complexitatea timp s timpul de executie al N este o functie

f : N N, definita prin:

f(n) = numarul maxim de pasi executati de N pentru un cuvant wIL(N) Sⁿ, nIN .

Notatia 2

f(n) = max = TIME_N(n)

Teorema 3

Fie t : N N cu proprietatea ca nIN: t(n) n.

=> NIMT nedeterminista cu o singura banda de intrare si cu timp de lucru t(n)

DIMT determinista cu o singura banda de intrare si cu timp de lucru 2^O(t(n)): L(D)=L(N).

demonstratie

Reluam procedura prin care - in teorema anterioara - am construit MT cu 3 benzi, M₃, pornind de la MT nedeterminista cu 1! banda, N. Incepem prin a examina arborele de derivare al lui N.

Fie o secventa de intrare oarecare wIS*, |w|=n, nIN. => Ii putem asocia un arbore de derivare in care sa figureze TOATE posibilitatile prin care N poate calcula w. Acest arbore are urmatoarele caracteristici:

(i) lungimea maxima a ramurilor de calcul este, cf.ip., t(n);

(ii) numarul maxim de descendenti ai unui nod oarecare este b, unde b=nr.max. de alegeri corecte din definitia functiei de tranzitie a lui N, d_N

=> (iii) numarul maxim de frunze ale acestui arbore este b^t(n) si

(iv) numarul total de noduri din acest arbore este de ordin O(b^t(n)).

Examinam acum modul in care M₃ simuleaza N.

Simularea presupune explorarea arborelui de derivare;

cf.ip.: N este decidenta

=> N se opreste pe orice intrare wIS

=> putem folosi oricare dintre metodele de parcurgere a arborilor (inclusv DEPTH-FIRST!)

=> putem aprecia ca timpul necesar atingerii unui nod plecand din radacina este O(t(n)) (cf. obs. (i));

=> timpul de lucru pentru M₃ este - cf.obs. (iv): O(t(n).b^t(n)) = 2^O(t(n))

=> timpul de lucru necesar convertirii M₃ la D (MT determinista cu 1! banda) este - cf. teoreme ant. : (2^O(t(n)))²=2^O(2.t(n))= 2^O(t(n)).

1. Clasa P; timpul polinomial
2. Exemple de probleme cu timp de calcul polinomial determinist

Complexitatea timp a problemelor se modifica

• cu un factor polinomial (o ridicare la patrat) atunci cand trecem de la MT cu mai multe benzi la MT cu o singura banda (ambele deterministe);
• cu un factor exponential atunci cand trecem de la MT nedeterministe la MT deterministe (ambele cu o singura banda).

Conceptul de calculabilitate si nu un model de calculabilitate in particular

• diferenta de comportament intre clasa functiilor de tip polinomial si clasa functiilor de tip exponential;
• diferentele de timp de lucru de tip polinomial sunt aproape nesemnificative in timp ce diferentele de tip exponential sunt importante

Toate modelele de calculabilitate deterministe "rezonabile" sunt POLINOMIAL ECHIVALENTE,

adica simularea unuia cu instrumentele celuilalt antreneaza doar o crestere polinomiala a timpului de lucru.

Definitia 1

Notam cu P clasa limbajelor decidabile in timp polinomial determinist de catre MT deterministe cu o singura banda de intrare:

Aceasta clasa de probleme are urmatoarele proprietati:

(a) este invarianta fata de toate modelele de calculabilitate care sunt polinomial echivalente cu MT deterministe cu o singura banda de intrare;

(b) corespunde clasei de probleme practic rezolvabile cu un calculator real.

Exemple de probleme cu timp de calcul polinomial determinist

Cateva precizari

• vom descrie algoritmii tot cu ajutorul etapelor si pasilor, ca si in cazul MT;
• vom calcula timpul de lucru al algoritmilor in 2 trepte:

vom cauta o limita superioara a numarului de etape si pasi executati de algoritm pe o intrare oarecare n I N,

vom examina fiecare pas al algoritmului pentru a determina daca poate fi implementat in timp polinomial, cu ajutorul unui model de calculabilitate determinist, "rezonabil",

intrucat compunerea a 2 polinoame este inca un polinom, vom putea conchide ca algoritmul ruleaza in timp polinomial;

• vom utiliza o metoda "rezonabila" de codificare a problemelor:

vom folosi tot codificarea sub forma unei secvente pe care o vom nota cu < >

vom aprecia ca o metoda de codificare este "rezonabila" daca ea foloseste un timp de lucru polinomial .

Teorema 1

Fie limbajul PATH = => PATH I P.

demonstratie

Urmatorul algoritm rezolva problema PATH in timp polinomial:

M = "Fie secventa de intrare <G,s,t>, unde G este un digraf oarecare iar s si t doua noduri oarecare ale sale:

1. Se marcheaza nodul s.

2. Se repeta Pasul 3 atat timp cat mai pot fi marcate noi noduri:

3. Se examineaza toate arcele din G : daca exista un arc (a,b) de la nodul marcat a la nodul nemarcat b atunci se marcheaza nodul b.

4. Daca t este marcat atunci M accepta secventa de intrare <G,s,t>, altfel respinge."

Analizam complexitatea timp a acestui algoritm:

(i)

• evident, prima si ultima etapa se executa o singura data;
• etapa a 3a se executa de cel mult m ori ;

T numarul total de pasi este 1 + m + 1, deci O(m).

(ii)

• prima si ultima etapa se implementeaza usor in timp polinomial, in oricare dintre modelele deterministe "rezonabile";
• etapa a 3a presupune o scanare a nodurilor si o testare a starii acestora: marcat / nemarcat; deci si aceste operatii se pot implementa in timp polinomial

T complexitatea timp a acestui algoritm de rezolvare a problemei PATH este polinomiala in raport cu numarul de noduri ale grafului.

=> O(1).O(1) + O(m).O(m²) + O(1).O(m) = O(m³).

Teorema 2

Fie limbajul RELPRIME=

=> RELPRIME I P.

demonstratie

(i)    construim o MT, E, care calculeaza cmmdc cu algoritmul lui Euclid

E = "Fie secventa de intrare <x,y>, x,yIN, reprezentate in baza 2:

1. Se repeta pasii 2 si 3 pana cand y=0:

2. Se atribuie x x mod y.

3. Se interschimba x si y.

4. Se returneaza x."

(ii)    construim o MT, R, care rezolva problema RELPRIME apeland MT, E, ca subrutina

R = "Fie secventa de intrare <x,y>, x,yIN, reprezentate in baza 2:

1. Se ruleaza E pe intrarea <x,y>.

2. Daca rezultatul returnat de E este 1 atunci R accepta, altfel: respinge."

(a)    demonstram ca fiecare executie a ciclului format din etapa a 2-a si etapa a 3-a (eventual cu exceptia primei executii) reduce valoarea lui x cel putin la jumatate

se executa etapa 2 => obtinem x<y (cf. def. operatorului mod)

se executa etapa 3 => obtinem x>y (pt ca x si y se interschimba)

se executa din nou etapa 2 => obtinem din nou x<y etc.

Distingem 2 cazuri:

• daca x/2 y x mod y < y x/2 => x se reduce cel putin la jumatate;
• daca x/2 < y x mod y = x-y < x/2 => x se reduce cel putin la jumatate.

(b)        calculam numarul de executii ale ciclului format din etapa a 2-a si a 3-a

fiecare executie a etapei 3 valorile lui x si y se interschimba

=> fiecare executie a ciclului valorile initiale ale x si y se reduc cel putin la jumatate, alternativ

=> numarul maxim de executii ale ciclului format din etapa 2 si 3 este

min .

Dar log₂x ~ |x_baza=2|

=> numarul de executii ale ciclului format din etapa 2 si 3 este de ordin O(n).

Fiecare etapa se executa intr-un singur pas

=> fiecare etapa utilizeaza un timp polinomial

=> timpul total de executie al algoritmului este polinomial

Teorema 3

LILIC => LIP.

Observatie

Teorema anterioara: LILIC este decidabil dar

algoritmul folosit in demonstratie ruleaza in timp exponential.

Justificare

Fie L I LIC => GIFNC astfel incat L=L(G) (cf. teorema anterioara).

Fie wIL, |w|=n, nIN; orice derivare in G pentru w va avea exact 2n-1 pasi

=> este suficient sa verificam toate derivarile de lungine 2n-1:

daca gasim o derivare care produce w, atunci MT accepta, altfel respinge.

Dar:

• lungimea derivarilor creste polinomial cu lungimea cuvintelor dar
• numarul derivarilor de lungime k, k I N; creste exponential cu lungimea derivarilor

=> trebuie cautat un algoritm care sa lucreze in timp polinomial;

Metoda programarii dinamice.

Informal

metoda programarii dinamice consta in rezolvarea problemei date prin rezolvarea subproblemelor de dimensiuni mari pe baza acumularii de informatii despre subproblemele de dimensiuni mici.

Formal

metoda programarii dinamice consta din determinarea solutiei prin luarea unui sir de decizii d₁,d₂, . ,d_n (unde d_i=transforma problema data din starea s_i-1 in starea s_i, i n) respectand principiul de optim (de minim sau de maxim).

Conform acestui principiu, daca d₁,d₂, . ,d_n este un sir optim de decizii care transforma problema data din starea initiala s₀ in starea finala s_n, atunci este indeplinita una dintre conditiile:

a) d_k, . ,d_n este un sir optim de decizii care duce problema din starea s_k-1 in starea s_n, k n;

b) d₁, . ,d_k este un sir optim de decizii care duce problema din starea s₀ in starea s_k, k n;

c) d_k+1, . ,d_n si d₁, . ,d_k sunt siruri optime de decizii care duc problema din starea s_k in starea s_n, respectiv din starea s₀ in starea s_k, k n.

Cazul (a): metoda 'inainte", ordinea deciziilor: d_n, d_n-1, . , d_1; d_i depinde de d_i+1, . ,d_n.

Cazul (b): metoda 'inapoi", ordinea deciziilor: d₁, d₂, . , d_n. d_i depinde de d₁,d₂, . ,d_i-1.

In cazul (c) spunem ca aplicam metoda mixta.

ideea demonstratiei

Vom considera urmatoarele subprobleme:

'fie o variabila oarecare A din GIFNC si fie un subcuvant oarecare v al lui w, wIL;

este adevarat ca A ==>* v ?'

Urmatorul algoritm va memora intr-o matrice patratica de ordin n x n, n=|w|, solutiile acestor subprobleme astfel:

i j n: celula (i,j) din matrice contine multimea variabilelor din G care genereaza subcuvantul w_iw_i+1 . w_j w.

Algoritmul completeaza celulele matricei pentru fiecare subcuvant al lui w, indiferent de lungimea acestuia:1,2, . ,k, . ,n=|w|;

• incepe cu celulele pentru cuvintele de lungime 1: (i,i), 1 i n = |w|;
• continua cu celulele pentru cuvintele de lungime 2: (i,i+1), 1 i n-1;
• apoi cu celulele pentru cuvintele de lungime 3 etc.,

folosind la completarea celulelor pentru subcuvintele de lungime k, 2 k n, informatia din celulele deja completate pentru subcuvintele de lungime 1,2,,k-1.

Sa presupunem, de exemplu, ca algoritmul a determinat ce variabile din G genereaza toate subcuvintele lui w de lungime cel mult k.

Pentru a determina daca o variabila oarecare A genereaza un subcuvant oarecare v de lungime k+1 al lui w, algoritmul:

(i) imparte acel subcuvant v in alte 2 subcuvinte nevide in toate cele k moduri posibile;

(ii) pentru fiecare divizare a lui v, algoritmul examineaza fiecare regula de tip A BC pentru a verifica daca:

• B genereaza 1⁰ subcuvant al lui v,
• C genereaza al 2-lea subcuvant al lui v

si face acest lucru folosindu-se de celulele deja calculate din matrice.

Daca atat B cat si C genereaza respectivele subcuvinte ale v,

=> A genereaza v

=> algoritmul adauga neterminalul A in celula corespunzatoare din matrice;

(iii) algoritmul incepe acest proces cu cuvintele de lungime 1, prin examinarea matricei pentru productiile de tipul A b.

demonstratie

Prezentam algoritmul, notat D:

Fie GIGIC, G in FNC, care genereaza LILIC si fie S simbolul de start al G.

D = 'Fie cuvantul de intrare w=w₁w₂ . w_n:

1. Daca w=l si daca productia S l se afla in G, atunci D accepta.                // este tratat cazul special al cuvantului vid

2. Pentru i=1,2, . ,n:

3. Pentru oricare variabila A din G:

4. Se verifica daca productia A b unde b=w_i se afla in G.

5. Daca da, atunci variabila A este depusa in celula (i,i) din matrice.

6. Pentru k=2, . ,n:                       // k = lungimea unui subcuvant v al lui w

7. Pentru i=1,2, . ,n-k+1:          // i = indicele initial (de start) al subcuvantului v din w

8. Fie j=i+k-1: // j = indicele final al subcuvantului v din w

9. Pentru t=i, . ,j-1            // t = indicele final al primului subcuvant al lui v w

10. Pentru orice productie A BC:

11. Daca celula (i,t) din matrice contine variabila B

iar celula (t+1,j) din matrice contine variabila C

atunci se depune variabila A in celula (i,j).

12. Daca variabila S apare in celula (1,n) din matrice, atunci D accepta, altfel D respinge.'

Analizam algoritmul din punct de vedere al complexitatii timp; observam ca el se compune din 4 etape: 1, 2, . , 6, . , 12.

Complexitatea alg. se obtine prin insumarea complexitatilor acestor etape:

• Etapele 1 si 12 se executa, evident, 1! data si au cate 1! pas;
• Pentru a calcula numarul de executii ale etapelor 2-5, procedam din aproape in aproape:

etapa a 2-a se executa de n=|w| ori;

pentru fiecare executie a etapei a 2-a, etapa a 3-a se executa de m ori, m=card(V) = nr. de variabile din G =>

pasii 4 si 5, cei mai 'interiori' din etapa a 2-a, se executa de n.m ori,

intrucat m = o constanta fixata, independenta de n

aceste etape sunt de ordin O(n);

• Pentru a calcula numarul de executii ale etapelor 6-11, procedam ca mai sus:

etapa a 6-a se executa de cel mult n ori;

pentru fiecare executie a etapei a 6-a, etapa a 7-a se executa tot de cel mult n ori;

pentru fiecare executie a etapei a 7-a, etapa a 8-a se executa 1! data iar etapa a 9-a se executa de cel mult n ori;

pentru fiecare executie a etapei a 9-a, etapele a 10-a si a 11-a se executa de cel mult r ori , unde r= numarul de productii din G;

intrucat r = o constanta fixata, independenta de n

etapa a 11-a - cea mai 'interioara' din algoritm - se executa de O(n³) ori;

=> algoritmul este de ordin O(1)+O(n)+O(n³)+O(1) = O(n³).

=> L I P.

1. Clasa NP
2. Exemple de probleme cu timp de calcul polinomial nedeterminist

Daca pentru unele probleme cu timp de calcul exponential s-au gasit - mai usor sau mai greu - algoritmi care ruleaza in timp polinomial, pentru altele astfel de algoritmi nu s-au gasit inca.

Totusi, cu privire la aceste probleme a fost facuta o constatare remarcabila:

asemenea rezolvabilitatii algoritmice si complexitatea unor probleme se afla in stransa relatie cu complexitatea altora

T descoperirea unui algoritm polinomial pentru o astfel de problema va permite rezolvarea in timp polinomial a unei clase intregi de probleme.

Exemplul 1: Problema drumului hamiltonian:

consta in a determina existenta unui drum hamiltonian (orientat) intre doua noduri oarecare s si t ale unui digraf oarecare, G.

Formalizat

HAMILTPATH

In demonstratia teoremei "PATH I P" algoritmul de cautare bruta (exponential) a fost inlocuit cu un alt algoritm, polinomial.

Nu se cunoaste inca un algoritm polinomial care sa rezolve HAMILTPATH.

Aceasta problema are o caracteristica interesanta:

• nu este rezolvabila in timp polinomial dar
• este verificabila in timp polinomial.

Daca determinam existenta un drum hamiltonian de la s la t - indiferent cum! -

putem apoi verifica existenta lui in timp polinomial,

verificand pur si simplu ca fiecare nod apare o data si numai o data:

i.e. un test care se executa in timp O(m²),

unde m = numarul de noduri din G.

Exemplul 2: Problema neprimalitatii unui numar:

consta in a determina daca un numar dat este compus sau nu.

Formalizat

COMPOSITES

nu se cunoaste un algoritm polinomial care sa decida asupra acestui limbaj

dar verificarea caracterului compus al unui numar natural se poate face in timp polinomial:

e suficient sa dispunem de un divizor propriu al acelui numar.

Observatia 1

Exista si probleme neverificabile in timp polinomial.

De exemplu, complementul problemei drumului hamiltonian:

Sa presupunem ca gasim un algoritm care sa determine inexistenta unui drum hamiltonian intr-un digraf G;

singura metoda prin care altcineva poate verifica inexistenta unui astfel de drum consta tot in aplicarea aceluiasi algoritm exponential care a determinat inexistenta drumului.

Definitia 1

Un verificator pentru limbajul L este un algoritm V cu proprietatea:

L =

Masuram timpul necesar unui verificator in functie de lungimea cuvantului w.

T Un verificator polinomial ruleaza in timp polinomial in raport cu lungimea cuvantului w.

Un limbaj L este polinomial verificabil daca admite un verificator polinomial.

Observatia 2

Cuvantul v I S* din definitie reprezinta informatia auxiliara utilizata de verificator pentru a verifica apartenenta cuvantului w I S* la limbajul L.

Acest cuvant se numeste certificat sau demonstratie a apartenentei la L.

Exemplul 3

HAMILTPATH

certificatul corespunzator secventei de intrare <G,s,t>IHAMILTPATH este insusi drumul hamiltonian de la s la t.

COMPOSITES : certificatul corespunzator numarului natural xICOMPOSITES este unul dintre divizorii acestuia.

In ambele cazuri, dandu-se certificatele corespunzatoare, verificatoarele pot verifica in timp polinomial apartenenta la limbajul respectiv a secventelor de intrare.

Teorema 1

VIP NIMT nedeterminista cu timp de lucru polinomial a.i. L(V)=L(N).

T

Fie L un limbaj care admite un verificator V polinomial.

Presupunem ca V este o MT care ruleaza in timp n^k si construim MT N astfel:

N = "Fie cuvantul de intrare w I S*, |w| = n:

1. Selectam in mod nedeterminist un cuvant v de lungime cel mult n^k.

2. Se ruleaza V pe intrarea <w,v>.

3. Daca V accepta <w,v> atunci si N accepta w; altfel respinge."

Din constructia de mai sus rezulta imediat ca N decide asupra limbajului L in timp polinomial si este echivalenta cu V.

Fie L un limbaj si N o MT nedeterminista care ruleaza in timp polinomial si decide asupra limbajului L .

Construim un verificator V polinomial pentru L astfel:

V = "Fie secventa de intrare <w,v>, unde w, v I S*, oarecari:

1. Se simuleaza N pe intrarea w; fiecare simbol din v este tratat ca o descriere a alegerii urmatorului nod din arborele de derivare (alegere care trebuie facuta la fiecare pas; a se vedea demonstratia teoremei de echivalenta dintre MT deterministe si MT nedeterministe).

2. Daca aceasta ramura de calcul a lui w din N accepta atunci si V accepta intrarea <w,v>, altfel respinge."

Din constructia de mai sus rezulta imediat ca verificatorul V este polinomial si echivalent cu N.

Definitia 2

Fie t : N ® R⁺.

Se defineste clasa de complexitate timp polinomial nedeterministic prin:

NTIME(t(n))

Definitia 3

NP este clasa limbajelor care admit verificatoare polinomiale.

NP este clasa limbajelor decidabile in timp polinomial de catre MT nedeterministe cu o singura banda de intrare

Observatia 3

• aratam ca fiecare etapa a algoritmului are o implementare in timp polinomial nedeterminist intr-un model de calculabilitate nedeterminist "rezonabil";
• aratam ca implementarea fiecarei ramuri de calcul necesita un numar de etape de ordin polinomial.

Exemple de probleme cu timp de calcul exponential

Teorema 2

HAMILTPATH I NP.

demonstratie

Construim o MT nedeterminsita NH care sa decida asupra limbajului HAMILTPATH in timp polinomial.

NH = "Fie secventa de intrare <G,s,t>, unde G este un digraf oarecare iar s, t sunt oricare doua dintre nodurile sale:

1. Se compune o lista de m numere naturale p₁, p₂, . , p_m, unde m = numarul de noduri ale G. Fiecare numar din lista este ales nedeterminist din multimea .

2. Daca lista contine repetitii, atunci NH respinge.

3. Se verifica daca s = p₁ si t = p_m; daca oricare dintre conditii nu are loc, atunci NH respinge.

4. Pentru fiecare i : 1 i m-1, se verifica daca (p_i, p_i+1) este un arc din G; daca cel putin una dintre conditii nu are loc atunci NH respinge intrarea <G,s,t>;

daca toate conditiile sunt indeplinite atunci NH accepta."

Analizam acest algoritm din punct de vedere al complexitatii timp:

etapa 1: generarea nedeterminista a numerelor p₁, p₂, . , p_m dintre numerele 1, 2, . , m

=> timp de lucru polinomial nedeterminist;

etapa 2: gasirea unei repetitii, cel putin

=> se fac teste de tipul p_i=p_j, unde i=1,2, . ,m-1 si j=i+1, . ,m => se executa cel mult m² teste;

etapa 3: efectuarea a 2 verificari

=> un factor constant, egal cu 2;

etapa 4: verificarea fiecareia dintre cele m.(m-1) perechi de numere generate nedeterminist (p_i, p_i+1) cu cele maximum m.(m-1) arce din G

=> se executa cel mult m⁴ teste.

T algoritmul ruleaza in timp polinomial nedeterminist.

Teorema 3

CLIQUE I NP.

demonstratie (1): cu verificator

Luand clica insasi ca certificat, contruim urmatorul verificator K pt CLIQUE:

K = "Fie secventa de intrare <<G,n>,C>:

1. Se testeaza daca C este un set de n noduri din G.

2. Se testeaza daca G contine toate muchiile care leaga nodurile din C.

3. Daca ambele teste sunt trecute, atunci K accepta; altfel, respinge."

demonstratie (2): cu MT nedeterminista

N = "Fie secventa de intrare <G,n>, unde G=(V,X) este un graf iar nI

1. Se alege in mod nedeterminist o submultime C de n noduri din G.

2. Se testeaza daca G contine toate muchiile care unesc intre ele cele n noduri din submultimea C V.

3. Daca da, atunci N accepta; altfel, respinge."

SUBSET-SUM = si ( astfel incat a_i=1^k y_i = t }

Exemplu: < , 25 > I SUBSET-SUM: 4 + 21 = 25

Teorema 4

SUBSET-SUM = si ( a.i. a_i=1^k y_i = t } I NP.

demonstratie (1): cu verificator

Luand subsetul insasi ca certificat, contruim urmatorul verificator S pt SUBSET-SUM:

S = "Fie secventa de intrare <<S,t>,C>:

1. Se testeaza daca C este o colectie de numere a caror suma este egala cu t.

2. Se testeaza daca S contine toate numerele care fac parte din C.

3. Daca ambele teste sunt trecute, atunci S accepta; altfel, respinge."

demonstratie (2): cu MT nedeterminista

N = "Fie secventa de intrare <S,t>:

1. Se alege in mod nedeterminist un subset C de numere din S.

2. Se testeaza daca C este un multiset ale carui elemente insumate sunt egale cu t.

3. Daca da, atunci N accepta; altfel, respinge."

Definitia 4

coNP

Observatia 4

coNP NP ?

1. P versus NP
2. NP-completitudine

P=NP

P NP P NP

T exista argumente atat in favoarea tezei P NP cat si in favoarea tezei P = NP .

P NP nu exista un algoritm rapid care sa inlocuiasca cautarea directa.

Cea mai buna metoda cunoscuta in prezent pentru a rezolva probleme din clasa NP in mod determinist necesita timp de lucru exponential

T putem demonstra ca:

Terminologie

NP = clasa problemelor rezolvabile algoritmic in timp polinomial nedeterminist

= clasa problemelor rezolvabile algoritmic in timp exponential determinist.

Teorema 1

P NP coNP

Observatia 1

P NP coNP

Observatia 2

P EXPTIME.

NP-completitudine

1970: Stephen COOK si Leonid LEVIN:

Probleme din clasa NP a caror complexitate proprie este strans legata de complexitatea intregii clase.

Aceste probleme se numesc NP-complete.

Fenomenul NP-completitudinii este important din punct de vedere:

• teoretic:
• practic:

Cercetatorii considera ca P NP

T demonstrarea faptului ca o problema este NP-completa este o dovada puternica a caracterului ei nepolinomial.

Exemplul 1: Problema evaluarii = satisfiabilitatii (Satisfiability Problem)

Definitia 1

O formula booleana se numeste satisfezabila=evaluabila

exista o combinatie de valori de adevar care, date variabilelor booleene din formula, evalueaza formula la valoarea 1.

Problema evaluarii (satisfiabilitatii) consta in a verifica daca o formula booleeana oarecare este evaluabila (satisfezabila) si se codifica prin:

SAT

Teorema 2 (Cook-Levin)

SAT I P P = NP

demonstratie

Metoda folosita: reductibilitatea polinomiala a timpului de lucru.

Definitia 2

Functia f: S S* se numeste polinomial calculabila

exista o MT cu timp de lucru polinomial: wIS*, se opreste, avand pe banda secventa f(w).

Definitia 3

Fie limbajele A, B S

Limbajul A se numeste polinomial reductibil la limbajul B

f : S S* polinomial calculabila astfel incat wIS

wIA f(w)I B.

Functia f se numeste reducerea polinomiala a lui A la B.

Notatia 1

A _P B

Teorema 3

Fie limbajele A, B S

Daca A _P B si BIP => A IP .

demonstratie

Cf. ip.: M = algoritm cu timp de lucru polinomial care decide B

Cf. ip.: f = reducere polinomiala a lui A la B

Construim urmatorul algoritm N care decide limbajul A:

N = " Fie secventa de intrare wIS

1. Se calculeaza f(w).

2. Se ruleaza M pe intrarea f(w); N returneaza exact ceea ce returneaza M."

Cf. ip. A _P B:   wIA f(w)IB    => M accepta f(w) wIA.                     (*)

N ruleaza in timp polinomial pt ca:                (**)

• etapa 1: reducerea f este polinomiala => timp polinomial
• etapa 2: avem o compunere de 2 polinoame => timp polinomial

Cf. (*) si (**): A IP .

Definitia 4

Fie limbajele A, B S

Limbajul B se numeste NP-complet

1. BINP;
2. AINP: A _P B.

Teorema 4

Fie limbajele A, B S

Daca B este NP-complet si BIP => P=NP.

demonstratie

Rezulta imediat din definitia reductibilitatii polinomiale

Teorema 5

Fie limbajele B, C S

Daca B este NP-complet si

C NP: B _P C

=> C este NP-complet.

demonstratie

Cf. ip.: B este NP-complet A NP: A _P B (cf. Def.4),

Cf. ip.: C NP: B _P C,

compunerea a 2 polinoame este tot un polinom

A _P C

=> C este NP-complet (cf. Def. 4).     

Clasa S

1. Definitii
2. Teorema lui Savitch
3. Clasele PSPACE si NPSPACE
4. PSPACE-completitudine

Definitie 1

Fie M o MT determinista cu 1! banda, decidenta,

wIS* un cuvant de intrare,

C=C₀C₁C₂ . C_dC_f un calcul oarecare efectuat de M pe intrarea w;

Complexitatea spatiu a M pe intrarea w este numarul intreg notat

SPACE_M(w) = min

= numarul minim de locatii de pe banda de intrare scanate de M pe intrarea w.

Definitie 2

Fie M o MT determinista cu 1! banda decidenta.

Complexitatea spatiu (determinist) a masinii Turing M este o functie

f : N N, definita prin:

f(n) = numarul maxim de locatii de pe banda de intrare scanate de M pentru orice secventa de intrare de lungime n, nIN .

Mai spunem ca M ruleaza intr-un spatiu de memorie egal cu f(n).

Notatia 1

f(n) = max = SPACE_M(n)

Definitie 3

Fie N o MT nedeterminista cu 1! banda, decidenta,

wIL(M) S

Complexitatea spatiu a N pe intrarea w este numarul intreg notat NSPACE_N(w) care reprezinta cel mai mic numar de locatii de pe banda de intrare scanat de N, dintre toate ramurile de calcul care accepta w.

Definitie 4

Fie N o MT nedeterminista cu 1! banda, decidenta,

Complexitatea spatiu (nedeterminist) a N este o functie

f : N N, definita prin:

f(n) = numarul maxim de locatii de pe banda de intrare necesar lui N pentru prelucrarea unui cuvant wIL(N) Sⁿ, nIN .

Notatia 2

f(n) = max = NSPACE_N(n)

Definitia 5

Fie f : N R+.

Definim clasele de complexitate SPACE(f(n)) si NSPACE(f(n)) astfel:

SPACE(f(n))

NSPACE(f(n))

Exemplul 1

Urmatorul algoritm rezolva SAT cu spatiu linear.

M₁ = "Fie secventa de intrare <f >, f = formula booleeana:

1. Pentru fiecare combinatie de valori de adevar atribuite variabilelor booleene x₁, x₂, . , x_m din f se executa Pasul 2:

2. Se evalueaza valoarea de adevar a formulei f

3. Daca f se evalueaza la 1, atunci M₁ accepta; altfel, respinge."

Evaluam complexitatea spatiu a M₁:

la fiecare iteratie a etapei a 2-a, M₁ trebuie sa memoreze numai combinatia curenta de valori de adevar ale variabilelor   x₁, x₂, . , x_m

=> M₁ utilizeaza aceeasi portiune a benzii de intrare

T spatiul necesar este de ordinul O(m).

Cum numarul de variabile m este mariginit superior de lungimea secventei de intrare

M₁ ruleaza in spatiu de ordinul O(n).

Exemplul 2

Fie AIAFN. Vrem sa verificam daca el accepta toate secventele din S*. Codificam aceasta problema prin urmatorul limbaj

ALL_AFN =

solutie

N = "Fie secventa de intrare <A>, unde A este un AFN:

1. Se marcheaza starea initiala a lui A.

2. Se repeta Pasul 3 de 2^q ori, unde q = |Q|.

3. Se selecteaza nedeterminist un simbol de intrare si se modifica pozitia marcajelor de pe starile lui A pentru a simula citirea acelui simbol.

4. Daca la pasii 2 si 3 apare o secventa pe care A o respinge (adica daca la un moment dat nici unul dintre marcaje nu se afla pe o stare de acceptare a lui A) atunci N accepta secventa de intrare <A>; altfel o respinge."

demonstram ca N decide

Daca exista secvente din S* pe care A le respinge

printre ele trebuie sa se afle una de lungime cel mult 2^q , deoarece in cazul tuturor secventelor de lungime mai mare, respinse de A, pozitiile markerilor descrisi in algoritmul de mai sus ar trebui sa se repete (A are prin ipoteza doar q stari).

Portiunea din secventa cuprinsa intre repetitii poate fi eliminata pentru a se obtine astfel o secventa respinsa, mai scurta.

=> N decide asupra limbajului.

calculam complexitatea spatiu a lui N

Algoritmul necesita spatiu de memorie suplimentar numai pentru stocarea locatiilor markerilor si a contorului de ciclare

=> algoritmul necesita spatiu linear

=> algoritmul ruleaza in spatiu nedeterminist de ordinul O(n).

Teorema lui Savitch

Unul dintre primele rezultate privind complexitatea spatiu:

MT deterministe (MTD) pot simula MT nedeterministe (MTN) utilizand o cantitate de memorie surprinzator de mica.

O astfel de simulare pare sa implice:

• din punct de vedere al complexitatii timp:

o crestere exponentiala: de la f(n) la 2^f(n),

• din punct de vedere al complexitatii spatiu:

o cresterea polinomiala: de la f(n) la f²(n).

Teorema lui SAVITCH

Fie o functie f: N R⁺ cu proprietatea: f(n) n

T NSPACE (f(n)) SPACE (f²(n))

demonstratie

vom rezolva o problema mai generala, PROBLEMA TRANZITIEI:

fie doua configuratii c₁ = uaq_rbv si c₂ = zcq_sdw (a,b,c,dIG, u,v,z,wIG*, q_r,q_sIQ) ale unei MTN si un numar tIN

trebuie sa verificam daca MTN poate trece din configuratia c₁ in configuratia c₂ in t pasi.

T Rezolvand PROBLEMA TRANZITIEI pentru

c₁ = configuratia de start a MTN;

c₂ = configuratia de acceptare a MTN;

t = numarul maxim de pasi pe care ii poate face MTN.

putem verifica daca MTN accepta secventa de intrare primita.

• se cauta o configuratie intermediara c_m,
• se verifica recursiv daca
• c₁ trece in c_m in t/2 pasi,
• c_m trece in c₂ in t/2 pasi.

Acest algoritm are nevoie de spatiu pentru a memora informatia din stiva recursiva.

Fiecare nivel al recurentei utilizeaza pentru memorarea unei configuratii un numar de locatii de memorie de ordinul O(f(n)).

Adancimea recurentei este log(t), unde t = timpul maxim utilizat de MTN pe o ramura oarecare de calcul.

Stim ca t = 2^O(f(n)) T log(t) = O(f(n))

=> simularea determinista necesita O(f(n)) . O(f(n)) = O(f²(n)) locatii de memorie.`

(i) Definim procedura TRANZ

Fie: w secventa de intrare primita de N,

t I N (pentru simplificare, putem presupune ca t este o putere a lui 2),

c₁, c₂ doua configuratii oarecare ale N;

atunci, TRANZ(c₁, c₂, t) accepta daca N poate trece din configuratia c₁ in configuratia c₂ printr-un calcul nedeterminist cu maximum t pasi; altfel respinge.

TRANZ = "Fie datele de intrare c₁, c₂ si t, ca mai sus:

1. Daca t = 1 atunci se verifica direct daca c₁ = c₂ sau daca c₁ trece in c₂ intr-un singur pas conform functiei de tranzitie a lui N.

Daca oricare dintre cele doua conditii este indeplinita atunci TRANZ accepta; daca nici una dintre conditii nu e indeplinita atunci TRANZ respinge.

2. Daca t > 1 atunci urmatoarele instructiuni se executa pentru fiecare configuratie c_m a lui N pe intrarea w si cu spatiu de lucru f(n):

3. Se ruleaza TRANZ(c₁, c_m, t/2).

4. Se ruleaza TRANZ(c_m, c₂, t/2).

5. Daca pasii 3 si 4 se incheie ambii cu acceptare, atunci TRANZ accepta.

6. Daca cel putin o data cele 2 conditii nu se indeplinesc, atunci TRANZ respinge."

(ii) Definim o MTD M care simuleaza N astfel:

• modificam N astfel incat atunci cand N accepta, N isi goleste banda de intrare si isi deplaseaza cursorul in celula cea mai din stanga, intrand astfel intr-o configuratie numita c_accept;
• notam cu c_start configuratia de start a lui N pe intrarea w ;
• alegem o constanta d I N astfel incat, pe intrarea w, unde |w|=n, N sa treaca prin maxim 2^df(n) configuratii si sa utilizeze f(n) celule de pe banda de intrare.

=> ne asiguram ca 2^df(n) este o limita superioara pentru timpul de lucru al oricarei ramuri de calcul a lui N pe intrarea w.

M = "Fie cuvantul de intrare w:

1. Returneaza rezultatul produs de TRANZ(c_start, c_accept, 2^df(n))."

(iii) corectitudinea lui M

algoritmul TRANZ rezolva PROBLEMA TRANZITIEI

M simuleaza corect N.

Mai trebuie sa demonstram ca M lucreaza cu spatiu O(f²(n)).

(iv) complexitatea lui M (aratam ca M lucreaza in spatiu O(f²(n)))

Procedura TRANZ se apeleaza pe ea insasi recursiv

la fiecare apel, ea memoreaza in stiva

• numarul de ordine al pasului de calcul curent,
• valorile lui c₁,c₂,t pt a le invoca la revenirea din apelul recursiv.

=> fiecare nivel de recurenta utilizeaza un spatiu de lucru suplimentar de ordinul O(f(n)).

In plus, la fiecare apel recursiv valoarea constantei t=nr. pasi = nr. config. necesare pentru calcularea w, se injumatateste (cf. procedurii).

Initial, t = 2^df(n)

T adancimea stivei (nr de apeluri recursive necesare) este O(log₂t)=O(log₂2^df(n))=O(d.f(n))=O(f(n))

T spatiul de memorie total este O(f(n)).O(f(n))=O(f²(n)).

(v) rezolvarea unei dificultati tehnice:

la fiecare apel recursiv al procedurii TRANZ, algoritmul M trebuie sa cunoasca valoarea lui f(n).

Solutia: modificam M astfel incat M sa incerce pe rand diverse valori pentru f(n): f(n) = 1, 2, 3, .

Pentru fiecare valoare f(n) = i, algoritmul M modificat utilizeaza TRANZ pentru a verifica daca N poate ajunge in final in configuratia c_accept, testand daca N ajunge in vreuna dintre configuratiile de lungime i+1.

De asemenea, M utilizeaza procedura TRANZ pentru a verifica daca N foloseste cel putin i+1 locatii, astfel:

fie f(n) = i; algoritmul M modificat utilizeaza procedura TRANZ pentru a verifica daca N poate ajunge din configuratia de start in una dintre configuratiile de lungime i+1 astfel:

daca nici una dintre configuratiile de lungime i+1 nu este atinsa atunci M respinge;

daca este atinsa una dintre configuratiile de lungime i+1 si aceasta este o configuratie de acceptare atunci M accepta;

daca este atinsa una dintre configuratiile de lungime i+1 si aceasta nu este o configuratie de acceptare atunci M continua cu f(n) = i+1.

(vi) algoritmul M modificat:

M' = " Fie secventa d eintrare wIS

1. Fie i=1.

2. Fie f(n)=i.

3. Fie c_a "prima" configuratie de lungime i+1 a lui N:

4. Se ruleaza TRANZ(c_start, c_a,2^d.i).

Daca TRANZ respinge si daca mai exista cel putin o configuratie de lungime i+1 netestata, atunci se reia Pasul 4.

Daca TRANZ respinge si daca nu mai exista nicio configuratie de lungime i+1 netestata, atunci M' respinge.

5. Daca TRANZ accepta si daca c_i+1=c_accept atunci M' accepta.

Daca TRANZ accepta si daca c_i+1 c_accept atunci i i+1 si se reia Pasul 2."

Clasele PSPACE si NPSPACE

Definitia 1

Notam cu PSPACE clasa limbajelor decidabile in spatiu polinomial de catre MT deterministe cu o singura banda de intrare:

Notam cu NPSPACE clasa limbajelor decidabile in spatiu polinomial de catre MT nedeterministe cu o singura banda de intrare:

Observatia 1

PSPACE = NPSPACE

(cf. Teoremei lui Savitch)

Exemplul 3

Cf. Ex.1: SAT I SPACE(n);

Cf. Ex.2:                                 

clasele de complexitate spatiu determinist sunt inchise la complementara => ALL_AFN I coNSPACE(n).

cf. Teorema Savitch => ALL_AFNISPACE(n²)

=> SAT, ALL_AFNIPSPACE

Conjectura privind relatia dintre clasele de complexitate timp si spatiu

(i) P PSPACE

Fie functia t: N N, t(n) n, ( ) n I N;

orice MT care ruleaza in timp t(n) poate utiliza cel mult t(n) celule de pe banda de intrare deoarece la fiecare pas de calcul ea nu poate examina decat cel mult o celula.

(ii) NP PSPACE

Cu un rationament analog rezulta ca NP NPSPACE.

Cf. Observatiei 1: PSPACE = NPSPACE => NP PSPACE.

(iii) Reciproc, putem gasi o majorare pentru complexitatea timp a unei MT in functie de complexitatea spatiu.

Cf. def. ant.: o configuratie a unui automat: C_i=uaq_ibv

Cf. lema ant: un automat linear marginit (ALM) cu r stari, care citeste un cuvant de lungime n de pe banda de intrare si care dispune de un alfabet de intrare S cu s elemente poate avea cel mult r.n.sⁿ configuratii distincte.

=> o MTIPSPACE (adica o MT care utilizeaza f(n) locatii de memorie, unde f : N N, f(n) n), poate avea cel mult f(n).2^O(f(n)) configuratii distincte.

Am pp ca MT se opreste indiferent de secventa de intrare primita

T MT nu cicleaza

=> pe parcursul oricarui calcul, nicio configuratie nu se repeta

T o MT care utilizeaza f(n) locatii de memorie trebuie sa execute f(n).2^O(f(n)) pasi de calcul, deci:

=> MTIPSPACE ruleaza in timp cel mult f(n).2^O(f(n))

=> MT IEXPTIME =>

Din (i), (ii) si (iii) rezulta ca:

P NP NPSPACE = PSPACE EXPTIME

Observatia 2

Nu se stie inca daca vreuna dintre incluziuni nu este de fapt chiar o egalitate.

S-ar putea descoperi oricand o simulare asemanatoare celei din demonstratia Teoremei lui Savitch care sa permita fuzionarea unora dintre aceste clase intr-o singura clasa.

Pe de alta parte, se demonstreaza ca P EXPTIME

T cel putin una dintre incluziunile de mai sus este stricta dar nu se stie care!!

In fapt, cei mai multi cercetatori cred ca toate incluziunile sunt stricte, adica accepta diagrama de mai sus ca descriind cel mai corect relatia dintre clasele de complexitate timp si spatiu:

PSPACE-completitudine

Definitia 2

Un limbaj B este PSPACE-complet

(1) B I PSPACE

(2) ( ) A I PSPACE A _P B ( A este polinomial reductibil la B)

Daca limbajul B satisface numai conditia (2) atunci spunem ca el este PSPACE-dificil (PSPACE-hard).

Observatia 3

PSPACE-completitudinea utilizeaza tot notiunea de reductibilitate in timp polinomial. Motivul:

T Regula este: oridecateori definim probleme complete pentru o anumita clasa de complexitate, modelul in raport cu care definim reducerea trebuie sa fie mai limitat (ca si complexitate) decat modelul folosit pentru definirea clasei de complexitate insasi.

Exemple de probleme PSPACE-complete

Problema 1: TBQF

Definitia 3

Formula booleeana complet cuantificata =

o formula booleeana in care fiecare variabila este cuantificata.

Exemplul 4

f x y [(x y) x y)]

Definitia 4

Problema TQBF consta in determinarea valorii de adevar a unei formule booleene complet cuantificate oarecare si este formalizata prin limbajul:

TQBF

Teorema 2

TQBF este o problema PSPACE-completa.

ideea demonstratiei

1. Pentru a demonstra ca TQBF I PSPACE construim un algoritm care asigneaza valori de adevar variabilelor din formula si apoi evalueaza recursiv valoarea de adevar a acesteia.

Pe baza acestei informatii, algoritmul poate determina daca formula data este sau nu adevarata.

2. Pentru a arata ca toate limbajele L din PSPACE se reduc polinomial la TQBF:

(i) construim pentru L o MT, M, cu spatiu de lucru polinomial,

(ii) construim o reducere polinomiala care asociaza o secventa unei formule booleeane complet cuantificate f care codifica o simulare a MT, M, pe acea intrare;

(iii) formula este adevarata M accepta.

Problema 2: Strategii de castig pentru jocuri

Fie o formula booleeana complet cuantificata

f x₁ x₂ x₃ . x_k [y

consideram un joc la care participa doi jucatori, E si U , care asigneaza pe rand valori de adevar variabilelor x₁, x₂, x₃, . ,x_k (in ordinea data de ordinea in care apar cuantificatorii) astfel:

• E asigneaza valori numai variabilelor cuantificate existential;
• U asigneaza valori numai variabilelor cuantificate universal.

Daca prin aceasta asignare formula y (partea lui f care nu contine cuantificatori) se evalueaza la TRUE, atunci castiga jucatorul E; altfel castiga jucatorul U .

Spunem ca jucatorul E are o strategie castigatoare pentru formula f daca - indiferent de asignarile facute de jucatorul U - jucatorul E poate asigna valori de adevar varibilelor (legate prin cuantificatori existentiali) in asa fel incat sa castige.

Este evident ca jucatorul E are o startegie castigatoare pentru f daca si numai daca f se evalueaza la valoarea 1. Avem astfel:

Teorema 3

Limbajul Formula-joc = este PSPACE-complet

Problema 3: Jocul geografic

Jocul geografic sau Antakhshari, se refera la numele oraselor.

El poate fi modelat printr-o problema de grafuri orientate:

• fiecare nod din digraf este etichetat cu numele unui oras
• exista un arc de la nodul u la nodul v daca ultima litera a etichetei nodului u coincide cu prima litera a etichetei nodului v.

Jocul incepe intr-un nod oarecare, fixat; cei doi jucatori se deplaseaza alternativ in digraf, de-a lungul arcelor, in noduri nevizitate inca. Jucatorul care nu reuseste sa faca o noua deplasare pierde.

Jocul poate fi generalizat la un digraf arbitrar (in care nodurile si arcele nu mai au nici o legatura cu orasele sau literele) si un nod predeterminat.

Problema consta in a determina daca primul jucator are o strategie castigatoare. Avem astfel:

Teorema 4

Limbajul Joc-geografic =

este PSPACE-complet.

ideea demonstratiei

Pentru a demonstra teorema ar trebui sa gasim o reducere in timp polinomial a problemei Formula-joc la problema Joc-geografic.

Intrucat se crede ca P PSPACE este de presupus ca nu exista nici un algoritm cu timp de lucru polinomial care sa-i permita primului jucator sa verifice existenta unei strategii castigatoare, cu atat mai putin sa o determine.