| CATEGORII DOCUMENTE |
| Astronomie | Biofizica | Biologie | Botanica | Carti | Chimie | Copii |
| Educatie civica | Fabule ghicitori | Fizica | Gramatica | Joc | Literatura romana | Logica |
| Matematica | Poezii | Psihologie psihiatrie | Sociologie |
Chiar daca o problema este rezolvabila algoritmic in principiu, exista posibilitatea ca obtinerea solutiei sa necesite cantitati mult prea mari de resurse de calcul: fie timp, fie memorie, fie ambele. Admitem atunci ca problema este nerezolvabila algoritmic in practica.
Abordam acum teoria complexitatii calculului, definind si studiind - dintre diferitele tipuri de resurse de calcul necesare rezolvarii problemelor - pe cele mai importante: timpul de calcul si spatiul de memorie.
Fie limbajul L | k
Am demonstrat ca L1 este independent de context si ca ACCGIC este decidabil; prin urmare stim ca L este decidabil (vezi si Teorema 2.9)
Problema care ne intereseaza acum este insa:
Fie o MT M clasica (cu o singura banda de lucru) care calculeaza L . Descriem aceasta MT in detaliu pentru a putea numara pasii pe care ii face:
M = "Fie cuvantul de intrare w I S
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.
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."
Numarul de pasi executati de un algoritm (o MT) pentru prelucrarea unei date de intrare si obtinerea rezultatului paote depinde de mai multi parametri. De exemplu, daca data de intrare a algoritmului este un graf, atunci numarul de pasi poate depinde de numarul de noduri / muchii, de gradul maxim al grafului, de o combinatie a acestor factori si / sau a altora.
Aici, pentru simplificare, vom calcula TIMPUL DE EXECUTIE al unui algoritm numai ca functie de LUNGIMEA SECVENTEI care reprezinta informatia sa de intrare si vom ignora ceilalti parametri. Se pot aborda:
cazul cel mai nefavorabil (in care se considera cel mai lung timp de executie al algoritmului pentru toate secventele de o lungime data);
cazul cel mai favorabil (in care se considera cel mai scurt timp de executie al algoritmului pentru toate secventele de o lungime data);
cazul mediu (in care se considera media timpilor de executie ai algoritmului pentru toate secventele de o lungime data).
1. Definitie
Fie M o MT oarecare care se opreste pentru orice secventa de intrare. Prin complexitate timp intelegem timpul de executie al M adica o functie
f : N N f(n) = numarul maxim de pasi executati de M pentru o secventa de intrare
de lungime n, ( ) n I N
Timpul exact de executie a unui algoritm poate fi o expresie foarte complexa; de aceea, de obicei, el este doar aproximat printr-o expresie mai simpla, continand numai termenul de ordinul cel mai mare si catre care tinde asimptotic (putem ignora termenii de ordin inferior si coeficientii deoarece, pentru intrari mari, acestia sunt dominati de termenii de ordin superior; vezi Observatia 6).
2. Exemplu
Fie f : N N f(n) = 5n + 2n + 22n + 6;
spunem ca f tinde asimptotic catre n si notam acest lucru cu O(n
3. Observatie
Notatia O a fost introdusa de P. BACHMANN in cartea sa "Analytische Zahlentheorie" in 1892, ca o notatie convenabila pentru operarea cu aproximatii. Ea ne permite sa inlocuim semnul cu semnul =. In general, notatia O(f(n)) poate fi utilizata oridecateori f este o functie de n , pentru a inlocui o anumita cantitate care nu este cunoscuta explicit.
Definitie
Fie f, g :
(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 n2 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)"
c g(n) f(n) c g(n)
f(n) = O(g(n)) si f(n) = W (g(n)).
n0
Spunem ca g este o limita asimptotica superioara, o limita asimptotica inferioara, respectiv o limita asimptotica pentru f.
5. Exemplu
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
f(n) = O (n ), de exemplu, pentru c = 1 si n = 6 sau pentru c = 36 si n
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.
6. Observatie
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) = O(n ) pentru ca O(n ) domina O(n). Sa mai observam ca fiecare aparitie a lui O poate reprezenta o alta constanta.
7. Observatie
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:
) x: 
2O(log n) este o limita superioara pentru nc, unde c este o
8. Observatie
Limitele asimptotice de tipul nc 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.
9. Observatie
Pe langa notatiile O si W mai exista si notatiile o si w , obtinute din Definitia 4 prin inlocuirea inegalitatii cu inegalitatea stricta < , sau
10. Exemple
n =o(n log log n)
n log log n = o(n log n)
n log n = o (n
n = o(n
11. Propozitie[1]
(i) Notatiile O, W Q o, w sunt tranzitive;
(ii) Notatiile O, W Q sunt reflexive, dar nu si o, w
(iii) Notatia Q este simetrica dar nu si celelalte notatii
12. Propozitie[2]
Notatiile O, W Q o, w pot fi manipulate algebric dar cu precautie:
c O(f(n)) = O(f(n))
O(f(n)) + O(f(m)) = O(f(n))
O(O(f(n))) = O(f(n))
O(f(n)) O(g(n)) = O(f(n) g(n))
O(f(n) g(n)) = f(n) O(g(n));
atentie: ultima "egalitate" are loc intr-un singur sens: de la stanga la dreapta.
Reluam MT care calculeaza L | k Fie | 0k k | = n.
Pentru a efectua prima etapa a algoritmului este nevoie de n pasi T O(n) pasi.
Aducerea cursorului in extremitatea stanga pentru a incepe bararea necesita alti 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 a patra, MT face o singura scanare pentru a hotari daca accepta / respinge secventa de intrare T se executa maximum n pasi (pentru secvente de tipul 011.1) T O(n) pasi.
T f(n) = O(n) + O(n) + O(n ) + O(n) = O(n
Observam ca in descrierea acestei MT nu am mentionat si repozitionarea cursorului in extremitatea stanga a secentei. Motivul: notatia asimptotica ne permite sa omitem din descrierea MT (algoritmului) acele detalii care afecteaza timpul de lucru al MT prin cel mult un factor constant.
13. Definitie
Fie t : N N. Se defineste clasa de complexitate TIME (timp polinomial) prin:
TIME(t(n))
1 Exemplu
L | k I TIME(n pentru ca M1 decide asupra L in timp O(n ) iar TIME(n contine toate limbajele asupra carora se poate decide in timp O(n ). Putem imbunatati aceasta limita? Putem defini o MT care sa decida asupra limbajului L mai repede?
(i) Modificam MT M astfel incat la fiecare Etapa 3 baram cate doua simboluri 0 si doua simboluri 1 (in loc de cate unul singur) 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 deci nu afecteaza timpul asimptotic de executie al algoritmului
(ii) Fie acum o alta MT M , definita astfel:
M2 = "Fie cuvantul de intrare w I S
1. Se examineaza banda de intrare si se respinge w daca se descopera un simbol 0 la dreapta unui simbol 1.
2. Se executa urmatoarele doua etape, atat timp cat pe banda exista atat simboluri 0 cat si simboluri 1:
3. Se scaneaza banda pentru a determina daca numarul total de simboluri 0 si 1 aflat pe banda este impar. Daca da, atunci cuvantul se respinge.
Se scaneaza banda si se bareaza simbolurile 0 din doi in doi incepand cu primul simbol 0 si se bareaza simbolurile 1 din doi in doi incepand cu primul simbol 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 MT M si M ; putem afirma deci ca M decide asupra limbajului L . calculam acum timpul sau de executie:
observam ca fiecare etapa se executa in O(n) pasi;
numaram de cate ori seexecuta fiecare etapa:
o Etapa 1 se executa o singura data,
o Etapa 5 se executa o tot singura data,
o in Etapa 4 se bareaza cel putin jumatate din simbolurile 0 si jumatate din simbolurile 1 la fiecare scanare 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+log2n) ori.
T timpul de executie pentru MT M este de:
O(n) + (1+log n) O(n) + O(n) = O(n) + O(n log n) = O(n log n)
T L I TIME(n log n)
(iii) Poate fi decis L in timp o n log n)? Raspunsul este negativ, conform Teoremei 3, data mai jos, fara demonstratie.
(iv) Limbajul L poate fi decis chiar in timp linear daca MT respectiva are doua benzi Fie MT M cu doua benzi definita astfel:
M = "Fie cuvantul de intrare w I S
1. Se examineaza banda de intrare si se respinge w daca se descopera un simbol 0 la dreapta unui simbol 1.
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..
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 secventa w se 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 secventa w se accepta."
Evident, M decide asupra limbajului L ; timpul sau de executie este O(n) deoarece fiecare etapa se executa o singura data si are nevoie de maximum n pasi.
Observam ca acest timp nu mai poate fi ameliorat pentru ca simpla citire a cuvantului de intrare necesita n pasi
15. Teorema
Orice limbaj care poate fi decis in timp o(n log n) de o MT cu o singura banda este regulat.
16. Observatie importanta
Calculul timpului de executie pentru MT care decide asupra limbajului L a pus in evidenta o problema interesanta:
cu o MT cu o singura banda, L este decidabil in timp O(n ) sau O(n log n);
cu o MT cu doua benzi, L este decidabil in timp O(n);
nici o MT cu o singura banda nu poate ameliora performanta de mai sus.
T complexitatea problemei L poate fi modificata daca gasim un algoritm mai eficient (o MT mai eficienta)
T complexitatea problemei L depinde de modelul de calculabilitate ales.
Aceasta evidentiaza o diferenta esentiala care exista intre teoria calculabilitatii si teoria complexitatii:
in teoria calculabilitatii, Teza Church-Turing arata ca toate modelele de calculabilitate "valabile" sunt echivalente intre ele (adica decid asupra aceleiasi clase de limbaje);
in teoria complexitatii, alegerea unui model de calculabilitate afecteaza complexitatea-timp a limbajului (problemei): un limbaj care - printr-un model de calculabilitate - este decidabil in timp linear poate sa fie - prin 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. Din fericire, necesarul de timp de calcul nu difera in mod esential la nivelul modelelor de calcul deterministe.
Vom examina modul in care alegerea unui model de calculabilitate sau a altuia afecteaza masura timp de complexitate a limbajelor (problemelor). Vom analiza trei modele de calculabilitate:
MT cu o singura banda (clasica);
MT cu mai multe benzi;
MT nedeterminista.
17. Teorema
Fie t : N N cu proprietatea ca ( ) n I N : t(n) n.
Atunci, orice MT M cu mai multe benzi si cu timp de lucru t(n) admite o MT S cu o singura banda de intrare si cu timp de lucru O(t (n)), echivalenta.
Demonstratie
Ideea demonstratiei
In Teorema 1.9 am aratat cum se poate transforma o MT M cu mai multe benzi intr-o MT S cu o singura banda, echivalenta.
Acum trebuie doar sa reluam demonstratia Teoremei 1.9 si sa analizam modul in care S simuleaza M pentru a calcula timpul suplimentar necesar. Vom demonstra ca simularea fiecarui pas efectuat de M necesita cel mult O(t(n)) pasi in cazul lui S. Prin urmare, timpul de executie total al lui M este de O(t (n)).
Formalizare
Fie M o MT cu k benzi de intrare care ruleaza in timp t(n), unde t : N N , t(n) n, ( ) n I N
Construim (dupa metoda utilizata in demonstratia Teoremei 1.9) o MT S cu o singura banda de intrare care sa simuleze M si analizam timpul de lucru care ii este necesar pentru aceasta.
Initial, S depune pe banda sa de intrare
continuturile celor k benzi al M, separandu-le printr-un
caracter special, # , care nu se
afla in alfabetul SS SM (a se vedea demonstratia Teoremei
1.9); in plus, S simuleaza pozitiile cursoarelor
lui M prin bararea simbolurilor corespunzatoare de pe banda sa (de fapt,
inlocuieste un simbol s cu s )s I GS GM
Apoi, S simuleaza pasii efectuati de M pentru un cuvant de intrare oarecare w I S*. 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 (simbolurile barate). 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. Daca unul dintre cursoarele reale ale M se deplaseaza la dreapta pe propria sa banda de lucru peste o celula vida (adica a parcurs complet propria sa secventa de intrare), atunci S trebuie sa-si mareasca spatiul alocat pe propria 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.
(i) 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).
(ii) Ulterior, S simuleaza fiecare dintre cei (conform ipotezei) t(n) pasi ai lui M.
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:
(S) = 1 + (M (M (Mk
1 + t(n) + 1 + t(n) + 1 + . + t(n) + 1 1 + k t(n) + k
Prin urmare, pentru a simula oricare dintre pasii lui M , S 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).
T timpul total necesar lui S pentru a simula un pas oarecare al lui M este de ordinul O(t(n)).
Dar conform ipotezei, M efectueaza t(n) pasi; prin urmare, in etapa propriu-zisa de simulare a lui M , S consuma un timp de calcul egal cu
t(n) x O(t(n)) = O(t (n))
Prin urmare, din (i) si (ii) rezulta ca intreaga simulare a lui M de catre S consuma
O(n) + O(t (n)) pasi
Dar, in ipoteza am presupus ca t(n) n, ( ) n I N. Aceasta inseamna ca putem aprecia timpul total de executie al lui S la O(t (n)). q.e.d.
18. Observatie
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!
In continuare, demonstram o teorema analoga pentru MT nedeterministe cu o singura banda de lucru. Aratam ca orice limbaj care este decidabil de catre o MT nedeterminista cu o singura banda de lucru este decidabil si de catre o MT determinista cu o singura banda, dar intr-un timp de executie semnificativ mai mare.
19. Definitie
Fie N o MT nedeterminista decidenta. Timpul de executie al N este o functie
f : N N, f(n) = numarul maxim de pasi efectuati de N de-a lungul oricarei
ramuri de calcul, pe intrarea w, |w| = n, ( ) w I S ) n I N
Aceasta definitie nu incearca sa modeleze o masina de calcul care exista in realitate ci este o definitie matematica utila pentru caracterizarea complexitatii unei clase importante de probleme de calculabilitate. De asemenea, aceasta definitie subliniaza faptul ca o MT nedeterminista decide aupra unui limbaj L daca toate ramurile sale de calcul se opresc, indiferent de intrarea primita.
MT determinista MT nedeterminsita
. .
f(n) . . f(n)
. . accepta
accepta / respinge respinge
20. Teorema
Fie t : N N cu proprietatea ca ( ) n I N : t(n) n.
Atunci, orice MT N nedeterminista cu o singura banda de intrare si cu timp de lucru t(n) admite o MT D determinsita cu o singura banda de intrare si cu timp de lucru 2O(t(n)), echivalenta.
Demonstratie
Fie N o MT nedeterminista cu o singura banda de intrare care ruleaza in timp t(n), unde t : N N , t(n) n, ( ) nIN
Construim (dupa metoda utilizata in demonstratia Teoremei 1.11) o MT D determinista cu o singura banda de intrare care sa simuleze N si analizam timpul de lucru care ii este necesar pentru aceasta.
Initial, am construit o MT determinista D' cu 3 benzi de lucru care poate fi apoi convertita intr-o MT determinista D cu o singura banda (dupa metoda data in demonstratia Teoremei 1.9; in plus, acum stim deja ca timpul de calcul necesar acestei ultime conversii este - conform Teoremei 17 - patratul timpului de lucru al MT cu mai multe benzi).
Fie un cuvant de intrare oarecare w de lungime n T ii putem asocia un arbore de derivare care sa figureze toate posibilitatile de calcul efectuate de N pentru w. Acest arbore de derivare are urmatoarele caracteristici:
(i) lungimea maxima a ramurilor de calcul (lungimea drumului de la radacina la o frunza) este de maximum t(n);
(ii) numarul maxim de descendenti ai unui nod oarecare este b, unde b = cardinalul maxim al unei imagini din definitia functiei de tranzitie a lui N:
d: Q x G P Q x G x ).
(iii) numarul maxim de frunze din acest arbore este bt(n) (conform (i) si (ii))
(iv) numarul total de noduri din acest arbore este mai mic decat dublul numarului de frunze, adica inferior lui 2 bt(n) T nr total de noduri din acest arbore este de ordin O(bt(n)
Analizam acum, din punctul de vedere al timpului de calcul necesar, modul in care D simuleaza N.
Simularea presupune explorarea arborelui de derivare; cum N este decidenta, inseamna ca se opreste pentru orice intrare, deci putem folosi oricare dintre metodele de parcurgere (chiar si Depth First!! alegem totusi parcurgerea Breadth First, adica vom vizita toate nodurile de pe nivelul d inainte de a vizita un nod oarecare de pe nivelul d+1). Putem incepe parcurgerea arborelui de la radacina si continua de-a lungul oricarui drum catre o frunza, oricat de ineficienta ar fi aceasta tehnica - expusa in demonstratia Teoremei 1.11). Conform observatiilor (i) - (iv), timpul necesar acestei parcurgeri (de la radacina la un nod oarecare) este de ordinul O(t(n)) si deci timpul de lucru al MT D' (determinista cu 3 benzi) este de ordinul O(t(n)bt(n) O(t(n)) (vezi Observatia 7).
Conversia lui D' intr-o MT D determinista cu o singura banda produce, conform Teoremei 17) o anumita crestere a timpului de calcul: de la O(t(n)) la O(t (n)).
Prin urmare, timpul de calcul total necesar conversiei unei MT nederministe cu o singura banda intr-o MT determinista cu o singura banda este de
q.e.d.
Cele doua teoreme de mai sus au ilustrat distinctii importante din punctul de vedere al complexitatii intre diferite modele de calculabilitate:
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);
complexitatea timp a problemelor se modifica cu un factor exponential atunci cand trecem de la MT nedeterministe la MT deterministe (ambele cu o singura banda).
In continuare, vom cerceta aceasta diferenta mai pe larg.
Diferenta dintre un algoritm cu timp de lucru polinomial si unul cu timp de lucru exponential este foarte importanta. Chiar pentru valori mici ale datelor de intrare (de exemplu, n = 1000) un algoritm cu complexitatea n poate rula si pe un calculator cu performante rezonabile deoarece necesita resurse de ordinul unui miliard in timp ce un algoritm cu complexitate 2n ar avea nevoie de resurse de ordinul 2 , numar care depaseste cu mult numarul de atomi din Univers!!
Algoritmii cu timp de lucru polinomial sunt - in majoritatea cazurilor - suficient de rapizi (eficienti), indiferent de gradul polinomului si de coeficientii implicati; algoritmii exponentiali sunt insa arareori utilizabili in practica. Algoritmii exponetiali apar atunci cand rezolvarea problemei propuse presupune o cautare bruta (cercetarea exhausitiva, secventiala a tuturor posibilitatilor, ca in cazul descompunerii unui numar in factori primi prin aplicarea definitiei: domeniul de cautare a divizorilor creste exponential cu numarul care trebuie descompus).
Toate modelele de calculabilitate deterministe "rezonabile" sunt polinomial echivalente, adica simularea unuia cu instrumentele celuilalt antreneaza doar o crestere polinomiala a timpului de lucru (nu putem formaliza termenul "rezonabil" dar il intelegem in sensul unei bune aproximari, corelatii cu calculatoarele din lumea reala).
In continuare ne vom concentra asupra acelor aspecte ale teoriei complexitatii-timp care nu sunt afectate, in ceea ce priveste timpul de lucru, de diferente de tip polinomial (le consideram nesemnificative si le ignoram, adica: daca atunci cand am introdus notatia asimptotica O am ignorat factorii constanti, acum, in aproximarea timpului de lucru, ignoram diferente polinomiale si mai importante, precum cea dintre n si n
T vom putea dezvolta teoria complexitatii timp intr-un mod care sa nu fie dependent de modelul de calculabilitate ales (scopul nostru este cercetarea proprietatilor fundamentale ale calculabilitatii si mai putin a proprietatilor MT sau a altui model particular).
Aceasta decizie nu implica desconsiderarea diferentelor de ordin polinomial in executia algoritmilor (stim bine cat de importanta este pentru programatori chiar o reducere cu 50% a timpului de executie al unui program), ci doar ca am ales aceasta aboradare - a distinctiei dintre timpul de lucru polinomial si timpul de lucru exponential - si nu alta.
21. Definitie
Notam cu P clasa limbajelor decidabile in timp polinomial 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.
Proprietatea (a) arata ca P este o clasa robusta (nu este afectata de modelul de calculabilitate particular ales);
Proprietatea (b) arata ca P are relevanta practica. Daca o problema P I P , inseamna ca dispunem de o metoda de a o rezolva in timp nk, pentru un k I N corespunzator. Daca putem sau nu sa utilizam efectiv metoda, aceasta depinde de valoarea lui k.
Evident, un timp de lucru de ordinul n nu este prea utilizabil in realitate. Totusi, stabilirea granitei rezolvabilitatii practice la nivelul polinomial s-a dovedit foarte utila: odata ce pentru o problema cu timp de calcul exponential s-a decoperit un algoritm de rezolvare cu timp de lucru polinomial inseamna ca s-a descoperit aspectul (cauza) care facea problema dificil de rezolvat (Atentie: nu am raspuns astfel intrebarii din cursul introductiv!!) si, in continuare, complexitatea algoritmului polinomial va putea fi redusa astfel incat problema sa devina efectiv rezolvabila.
22. Cateva precizari
vom descrie algoritmii, tot ca in cazul MT, cu ajutorul etapelor si pasilor;
vom calcula timpul de lucru al algoritmilor in 2 trepte:
o vom cauta o limita superioara a numarului de etape si pasi executati de algoritm pe o intrare oarecare n I N
o vom examina fiecare pas al algoritmului pentru a determina daca poate fi implementat in timp polinomial, cu ajutorul unui model de calculabilitate determinist, "rezonabil",
o cum 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 (de exemplu, codificarea numarului natural 17 ca o secventa de 17 simboluri 1 nu este rezonabila pentru ca timpul de codificare creste exponential cu valoarea datei de intrare!!). In general, metodele clasice de codificare a grafurilor, multimilor, automatelor etc., sunt "rezonabile": matricea de adiacenta, lista nodurilor si a muchiilor, etc. Cum, in ambele aceste reprezentari ale grafurilor, dimensiunea grafului (si deci a reprezentarii) este determinata in mod esential de numarul de noduri, vom aprecia complexitatea timp a unor probleme de grafuri in raport cu numarul de noduri ale grafului si nu cu lungimea reprezentarii acestuia.
Prima problema pe care o studiem se numeste PATH si consta in a determina existenta unui drum intre doua noduri oarecare s, t ale unui graf G.
23. Teorema
PATH I P
Demonstratie
Ideea demonstratiei
Un algoritm care rezolva problema prin cautare directa nu este suficient de rapid: el trebuie sa examineze toate drumurile din G pentru a veda daca exista unul, orientat, de la s la t , adica trebuie sa examineze un numar de mm drumuri, unde m = numarul de noduri din G (cel mai lung drum - cel hamiltonian - are m noduri, pentru ca ciclurile nu sunt nici semnificative nici permise)
T acest algoritm este exponential, deci neinteresant.
Pentru a evita cautarea bruta vom utiliza una dintre metodele de parcurgere a grafului, de exemplu Breadth First, si vom marca toate nodurile care pot si atinse din nodul s prin drumuri de lungime 1 (arce), 2, 3, . , m. Vom demonstra ca aceasta strategie este limitata superior de un polinom.
Formalizare
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 urmator atat timp cat mai exista noduri nemarcate:
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.
Daca t este marcat atunci M accepta secventa de intrare <G,s,t>, altfel respinge."
Analizam complexitatea timp a acestui algoritm:
(i)
o evident, prima si ultima etapa se executa o singura data;
o etapa a 3a se executa de cel mult m ori (pentru ca de fiecare data - cu exceptia ultimeia - se marcheaza un nod din G iar G are, prin ipoteza, m noduri;
T numarul total de pasi este 1 + m + 1, deci O(m).
(ii)
o prima si ultima etapa se implementeaza usor in timp polinomial, in oricare dintre modelele deterministe "rezonabile";
o 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 q.e.d.
2 Teorema
RELPRIME I P
Demonstratia: exercitiu
25. Teorema
Orice limbaj independent de context este decidabil in timp polinomial, adica
) L I LIC T L I P
Demonstratia: se utilizeaza metoda programarii dinamice; timpul de calcul este de ordin O(n ), unde n = lungimea cuvantului de intrare.
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. MOTIVUL NU ESTE CUNOSCUT:
o poate pentru unele dintre ele astfel de algoritmi polinomiali exista dar nu au fost inca descoperiti pentru ca - probabil - folosesc principii si metode inca necunoscute;
o poate ca unele dintre ele pur si simplu nu pot fi rezolvabile in timp polinomial (sunt intrinsec dificile).
Totusi, cu privire la aceste probleme a fost facuta o constatare remarcabila:
T descoperirea unui algoritm polinomial pentru o astfel de problema va permite rezolvarea in timp polinomial a unei clase intregi de probleme.
Vom studia mai atent acest fenomen, incepand cu un exemplu, numit HAMILTPATH. Aceasta problema consta in a determina existenta unui drum hamiltonian (orientat) intre doua noduri oarecare s si t ale unui digraf G.
Formalizat:
HAMILTPATH
In demonstratia Teoremei 23 (PATH I P ) algoritmul de cautare bruta (exponential) a fost inlocuit cu un alt algoritm, polinomial. Daca modificam algoritmul de cautare directa astfel incat sa verificam nu numai existenta unui drum de la s la t ci si faptul ca acesta trece prin fiecare nod din G exact o singura data, am rezolvat problema dar in timp exponential!! 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 - adica un test care se executa in timp O(m ), unde m = numarul de noduri din G).
O alta problema verificabila in timp polinomial este problema neprimalitatii unui numar (a caracterului sau de numar compus). Formalizat:
COMPOSITES
Desi nu se cunoaste un algoritm polinomial care sa decida asupra acestui limbaj (care sa rezolve problema neprimalitatii), verificarea caracterului compus al unui numar natural se poate face foarte usor (in timp polinomial): e sufiecient sa dispunem de un divizor propriu al acelui numar
26. Observatie
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.
27. Definitie
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 fata de lungimea cuvantului w.
Un limbaj L este polinomial verificabil daca admite un verificator polinomial.
28. Observatie
Cuvantul v I S* din Definitia 27 reprezinta informatia auxiliara utilizata de verificator pentru a verifica apartenenta cuvantului w I S* la limbajul L. Acest cuvant se numeste certificat sau dovada a apartenentei la L.
Sa remarcam faptul ca, in cazul verificatoarelor polinomiale, certificatele au o lungime polinomiala in functie de lungimea lui w deoarece aceasta este singura informatie accesibila verificatoarelor in timpul limitat de care dispun.
29. Exemple
In cazul problemei HAMILTPATH, certificatul corespunzator secventei de intrare <G,s,t> I HAMILTPATH este insusi drumul hamiltonian de la s la t.
In cazul problemei COMPOSITES, certificatul corespunzator numarului natural x I COMPOSITES 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.
30. Teorema
Pentru orice verificator polinomial putem construi o MT nedeterminista cu timp de lucru polinomial echivalenta si reciproc.
Demonstratie
Ideea demonstratiei
O MT nedeterminista cu timp de lucru polinomial (pe scurt: o MT nedeterminsita polinomiala) simuleaza un verificator polinomial "ghicind" certificatul.
Un verificator simuleaza o MT nedeterminista polinomiala folosind ca certificat ramura de calcul care accepta.
T
Fie L un limbaj care admite un verificator V polinomial.
Presupunem ca V este o MT care ruleaza in timp nk 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 nk
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 1.11).
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. q.e.d.
31. Definitie
Fie t : N N Se defineste clasa de complexitate NTIME (timp polinomial nedeterministic) prin:
NTIME(t(n))
32. Definitie
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:
33. Observatie
Importanta clasei NP rezida in faptul ca ea inglobeaza o serie intreaga de probleme importante din punct de vedere practic. Si ea este invarianta la alegerea oricarui model de calculabilitate "rezonabil" (deoarece toate aceste modele sunt polinomial echivalente).
Vom descrie si analiza algoritmii nedeterministi cu timp de calcul polinomial dupa metoda folosita in cazul algoritmilor polinomiali deterministi:
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.
3 Teorema
HAMILTPATH I NP
Demonstratie
Construim o MT nedeterminsita NH care sa decida asupra limbajului HAMILTPATH in timp polinomial.
Conform Definitiei 19, timpul de lucru al unei MT nedeterministe este dat de numarul de pasi necesari celei mai lungi dintre ramurile calculului nedeterminist. Atunci, definim NH astfel:
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 , . , pm, unde m = numarul de noduri ale G. Fiecare numar din lista este ales nedeterminist din multimea
2. Daca lista contine repetitii, atunci NH respinge intrarea.
3. Se verifica daca s = p si t = pm; daca oricare dintre conditii nu are loc, atunci NH respinge intrarea.
Pentru fiecare i : 1 i m-1, se verifica daca (pi, pi+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:
prima etapa consta dintr-o generare nedeterminista a numerelor p , p , . , pm dintre numerele 1, 2, . , m T timp de lucru polinomial nedeterminist;
etapa a doua consta din gasirea unei repetitii, cel putin, deci se fac teste de tipul pi=pj, unde i = 1, 2, . , m-1 si j = i+1, . , m T se executa cel mult m teste
etapa a treia consta din 2 verificari T un factor constant egal cu 2;
etapa a patra consta din verificarea fiecareia dintre cele m (m-1) perechi de numere generate nedeterminist (pi, pi+1) cu cele maximum m (m-1) arce din G T se executa cel mult m teste.
T algoritmul ruleaza in timp polinomial nedeterminist.
O alta problema de teoria grafurilor, problema clicilor, consta in a determina daca un graf dat contine o clica de o anumita dimensiune.
CLIQUE I NP.
O problema de aritmetica numerelor intregi, problema submultimilor suma, consta in a determina daca un multiset dat contine un submultiset ale carui elemente insumate sunt egale cu un numar natural dat.
SUBSET-SUM = si (
astfel incat ayi = t }
De remarcat ca si sunt multiseturi nu multimi obisnuite.
De exemplu, < , 25 > I SUBSET-SUM deoarece 4 + 21 = 25
Nu rezulta imediat ca multimile 
si 
fac parte din NP. E mai dificil sa
verificam absenta unui elemnt decat prezenta lui intr-o
multime!
37. Definitie
coNP este clasa limbajelor care sunt complementarele unor limbaje din NP.
Nu se stie daca coNP este diferit de NP
Problema daca P = NP este una dintre cele mai importante probleme nerezolvate din informatica teoretica si din matematicile contemporane.
Reamintim:
P = clasa limbajelor pentru care apartenenta poate fi decisa in timp de lucru polinomial determinist;
NP = clasa limbajelor pentru care apartenenta poate fi decisa in timp de lucru polinomial nedeterminist (sau verificata in timp de lucru polinomial determinist).
am considerat - informal - ca rezolvabilitatea in timp polinomial este o rezolvabilitate rapida.
Puterea
verificatoarelor polinomiale pare mult mai mare decat puterea MT decidente polinomiale.
T exista argumente atat in favoarea tezei P NP cat si in favoarea tezei P = NP
Curios, pare mai dificil de demonstrat ca P NP pentru ca ar insemna sa demonstram ca nu exista un algoritm rapid (cu timp de lucru polinomial determinist) 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:
dar nu stim daca NP este continuta intr-o clasa de complexitate timp determinista mai mica decat EXPTIME.
38. Terminologie
Totusi, din motivul de mai sus si pe baza Teoremei 20, putem face un "abuz" si putem sa ne referim in continuare la NP
fie ca la clasa problemelor rezolvabile algoritmic in timp polinomial nedeterminist,
fie ca la clasa problemelor rezolvabile algoritmic in timp exponential determinist.
Mai mult, in continuare, vom considera
P drept clasa problemelor rezolvabile algoritmic in timp de lucru polinomial (determinist),
NP drept clasa problemelor rezolvabile algoritmic in timp de lucru exponential (determinist).
Dam fara demonstratie urmatoarea teorema[9]:
39. Teorema
P NP coNP
De fapt, se crede ca P NP coNP
Figura de mai jos descrie relatiile despre care se presupune ca exista intre clasele de complexitate definite mai sus. Se crede ca toate incluziunile sunt stricte; singurul caz in care se poate si demonstra este P EXPTIME
Un pas important in problema relatiei dintre clasele P si N a fost facut la inceputul anilor 1970 de catre cercetatorii Stephen COOK si Leonid LEVIN: ei au identificat o serie de probleme din clasa NP a caror complexitate proprie este strans legata de complexitatea intregii clase.
Daca s-ar descoperi un algoritm cu timp de lucru polinomial pentru oricare dintre aceste probleme,atunci toate problemele din NP ar fi rezolvabile in timp polinomial (determinist). De aceea, aceste probleme se numesc NP-complete.
Fenomenul NP-completitudinii este important din punct de vedere:
teoretic:
o un cercetator care incearca sa demonstreze ca P NP ar trebui sa se concentreze asupra unei probleme NP-complete (dintre problemele din NP , acestea sunt cele care solicita mai mult decat restul problemelor, un timp de lucru superior celui polinomial),
o un cercetator care incearca sa demonstreze ca P = NP si-ar atinge scopul prin simpla gasire a unui algoritm polinomial (determinist) pentru una dintre problemele NP-complete;
practic:
o fenomenul NP-completitudinii poate evita pierderea timpului cu cautarea unui algoritm polinomial (determinist) pentru o anumita problema, algoritm care de fapt nu exista.
Desi nu putem inca demonstra ca o anumita problema este nerezolvabila algoritmic in timp polinomial, credem ca P NP T demonstrarea faptului ca o problema este NP-completa este o dovada puternica a caracterului ei nepolinomial.
39. Definitii
O formula booleeana este o expresie care contine variabile booleene, constantele booleene 0 si 1 si operatorii booleeni
O formula booleana (de exemplu: ( x y) (x z) se numeste evaluabila exista o combinatie de valori de adevar care, date variabilelor booleene din formula, evalueaza formula la valoarea 1 (altfel spus: "fac formula adevarata"). Spunem ca acea combinatie de valori satisface formula.
Problema evaluarii (sau a satisfiabilitatii) consta in a verifica daca o formula booleeana oarecare este evaluabila[12] (satisfezabila) si se codifica prin:
SAT
40. Teorema (Cook-Levin)
SAT I P P = NP
Demonstratie
Metoda folosita este reductibilitatea polinomiala a timpului de lucru, unde
41. Definitie
Functia f: S S* se numeste calculabila in timp polinomial (prescurtat: polinomial calculabila) exista o MT cu timp de lucru polinomial care, oricare ar fi secventa de intrare w I S*, se opreste, avand pe banda secventa f(w).
42. Definitie
Fie limbajele A, B S*. Limbajul A se numeste reductibil functional in timp polinomial (prescurtat polinomial reductibil) la limbajul B si se noteaza prin A P B ) f : S S* polinomial calculabila astfel incat ( ) w I S*: w I A f(w) I B.
Functia f se numeste reducerea polinomiala a lui A la B.
Un drum hamiltonian intr-un digraf G este un drum care trece prin fiecare nod al digrafului o data si numai o data.
De curand a fost descoperit un algoritm de determinare a caracterului compus sau prim al unui numar; acest algoritm este insa mult mai complicat decat metoda de verificare a caracterului compus al unui numar, descrisa mai sus.
Fie G un graf neorientat. O clica in G este un subgraf al lui G cu proprietatea ca intre oricare doua noduri ale sale exista o muchie. O n-clica este o clica avand n noduri.
Problema clicii consta in a determina daca un graf dat contine o clica de o anumita dimensiune.
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2336
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
