================= 30.9.2003 ====================
spot�eba zdroj� - �as, pam�
p��klady:
- SAT (nejhor�� p��pad 2^n, �asto lze l�pe, zchaff)
- t��d�n� (bublinkov�, stromem, heap-sort - n log n, �asto se pou��v� shellsort - n^1.5)
- n�soben� n^2, n log n log log n (zcela jin� speci�ln� algoritmy pro hardware)
- n�soben� matic (n^3, Strassen, dal�� zlep�en�, 2+eps hypot�za)
- testov�n� prvo��selnosti
- probl�m zastaven� v dan�m �ase
- Presburgerova aritmetika, re�ln� aritmetika
- obti�nost inverze MD5
v�po�etn� modely
- TS + varianty
- RAM + varianty
formalizace pojmu �loha
- obecn� �loha (sigma1 -> sigma2)
- rozhodovac� �loha
- optimaliza�n� �loha
me�en� slo�itosti
- nejhor�� versus pr�m�rn� p��pad
(nejhor�� je �asto p��li� pesimistick�, pr�m�rn� z�vis� na volb�
rozd�len�, kter� je �asto neznam�)
- odhad slo�itosti pomoc� funkce z�visej�c� na d�lce vstupu versus
odhad slo�itosti pro vstupy fixovan� d�lku vstupu
(Existuj� p��klady, kdy asymptotick� slo�itost je vzd�len� slo�itosti
v praktick�ch situac�ch. Asymptotika je ale d�le�it�, pokud chceme
z�skat alespo� n�jak� obecn� nadhled nad situac�.)
================= 7.10.2003 ====================
P�edm�t zkoum�n�: asymptotick� slo�itost rozhodovac�ch �loh na TS
(p�edev��m polynomi�ln� �as, nedeterministick� polynomi�ln� �as,
polynomi�ln� prostor)
k�dov�n� vstupu pomoc� slov v kone�n� abeced�, probl�m efektivn�ho k�dov�n�.
Vztah obecn�ch �loh a rozhodovac�ch �loh: hled�n� spl�uj�c�ho
ohodnocen�, Hamiltonovsk� kru�nice, obecn� v�ta o ekvivalenci
z hlediska polynomi�ln�ch �loh.
V d�kazu t�to v�ty jsme trochu p�edb�hli n�kter� pojmy:
- p�edpokl�d�me p�edb�nou znalost toho, co je to jazyk rozpozn�van� TS
- jako slo�itost pou��v�me p�edstavu o po�tu operac� na b�n�m po��ta�i
bez p�esn� definice. Pozd�ji tuto slo�itost nahrad�me RAM s jednotkovou
m�rou slo�itosti.
Turing�v stroj
jednostrann� p�sky,
vstupn� (n�kdy jen ke �ten�)
pracovn�
v�stupn� (jen z�pis)
instrukce s k-ticemi q,a,a,s,q
koncov� stavy q-plus, q-minus
p�ij�m�n� koncov�m stavem q-plus
zam�tnut� nedefinovan�m p�echodem (nen� def. instrukce nebo p�echod mimo p�sku)
m��en� �asov� slo�itosti
vstupn� p�ska m��e b�t pou�ita k z�pisu
m��� se po�et krok�
m��en� prostorov� slo�itosti
vstupn� p�ska jen pro �ten� (umo��uje definovat prostor men�� ne� n)
me�� se maximum po�tu nav�t�ven�ch pol� na jednotliv�ch pracovn�ch p�sk�ch
RAM
registry r_i \in Z
vstupn� posloupnost v_i \in Z
��d�c� jednotka
program pi_1, pi_2,...
��ta� instrukc� kappa
p��klad �lohy, kde je v�cep�skov� stroj efektivn�j��, je kop�rov�n�
del��ho �seku p�sky.
================= 14.10.2003 ===================
parametry a instrukce RAM
m��en� slo�itosti (jednotkov�, logaritmick�)
Booleovsk� obvody, posloupnosti obvod�, rozd�l proti formul�m
-- vynech�no k�dov�n� obecn�ch slov --
================= 21.10.2003 ===================
zopakov�n� m�r slo�itosti na RAM, souhrnn� diagram pl�novan�ch simulac�
simulace v�cep�skov�ho stroje na jednop�skov�m - program v pseudok�du
================= 4.11.2003 ====================
p�ipomenut diagram transformac� 1-TS, m-TS, RAM j.m.s.p.o., RAM l.m.
k <= b <= kO(log k) (p�i spln�n� p.o.)
simulace RAM na 6-TS
p�sky: vstupn�, pam�, adresovac�, 3 aritmetick�
program pro RAM vyj�d��me jako v�vojov� diagram
blok ka�d� instrukce p�ep��eme na TS (u skok� budou m�t dva mo�n� v�stupy)
t�m z�sk�me v�vojov� diagram pro simuluj�c� TS
z n�j z�sk�me TS
�asov� slo�itost simulace jedn� instrukce
bitov� slo�itosti jednotliv�ch instrukc�: b_i, b = \sum b_i
�ten� z pam�ti a z�pis do pam�ti O(s), s = \sum b_i
aritmetick� operace O(b_i^2)
sou�et p�es v�echny instrukce \sum b_i^2 + k \sum b_i \le 2 (\sum b_i)^2
pokud b_i \le O(log k), pak tak� omezeno O(k^2 log k)
================= 11.11.2003 ===================
Simulace polynomi�ln� omezen�ho TS polynomi�ln� velk�mi obvody.
TS s pomocnou funkc�, ekvivalence P/poly a polynomi�ln� velk�ch obvod� bez d�kazu.
P��klady �loh se snadno verifikovateln�mi d�kazy kladn� odpov�di: SAT, klika.
Polynomi�ln� omezen� relace, definice t��dy NP, polynomi�ln� p�evoditelnost.
Probl�m SAT je p�evoditeln� na probl�m kliky.
================= 18.11.2003 ===================
Dokon�en� d�kazu p-p�evoditelnosti SAT na probl�m kliky.
Vsuvka: Pokud formule v KNF m� m klausul�, kter� maj� d�lky k_1, k_2, ..., k_m,
pak plat� implikace
\sum_i 1/2^{k_i} < 1 => formule je splniteln�
Nap�. p�i d�lk�ch 3,3,3 je
\sum_i 1/2^{k_i} = 3/8 < 1
a formule je tedy splniteln�.
p-p�evoditelnost je tranzitivn�.
L_1 p-p�evoditeln� na L_2, L_2 \in P => L_1 \in P
Definice NP-�pln� �lohy.
Pokud je L NP-�pln�, pak L \in P <=> P = NP
Pokud jsou L_1 a L_2 NP-�pln�, pak L_1 \in P <=> L_2 \in P
Cookova v�ta: SAT je NP-�pln�
Pro libovolnou danou NP-�lohu L jsme zkonstruovali funkci g_L(w), jej�� hodnotou
je Booleovsk� obvod a kter� d�v� p-p�evoditelnost L na probl�m splnitelnosti obvod�.
Dota�en� p�evodu a� na splnitelnost formul� (SAT) p���t�.
================= 25.11.2003 ===================
Splnitelnost obvod� je p-p�evoditeln� na SAT.
D�sledek: SAT je NP-�pln�.
SAT je p-p�evoditeln� na 3-SAT.
D�sledek: 3-SAT je NP-�pln�.
Pro porovn�n�: 2-SAT je v P.
(k,s)-SAT, formulace v�ty o skoku v parametru s.
D�kaz splnitelnosti ka�d� (k,k)-SAT instance z Hallovy v�ty.
================== 2.12.2003 ==================
P�edn�ka odpadla.