PR�B�H P�EDN��KY V�PO�TOV� SLO�ITOST (LETN� SEMESTR 2004/2005)

============================  24.2.2005  ===============================

(3,3)-SAT m� v�echny instance splniteln�.
(3,4)-SAT je NP-�pln�.
Obecn� v�ta:
  Pokud existuje nesplniteln� (s,k)-formule, pak (s,k)-SAT je NP-upln�.
D�sledek: Pro ka�d� s existuje k(s) tak, �e
  (s,k(s)-1)-SAT m� v�echny klausule splniteln�
  a (s,k(s))-SAT je NP-�pln�.

============================  3.3.2005  ===============================

Jednozna�nost z�pisu polynomu jako kombinace monom�.
Multiline�rn� polynomy jako funkce vhodn� pro postupn� zjednozna��ov�n�
  pravd�podobnostn�ch �e�en� �loh optimalizace.
Pravd. aproxima�n� algoritmus pro MAX-SAT s apr. faktorem 1/2 (postup I).
Jeho derandomizace.
Postup II: p�evod na celo��seln� programov�n�, relaxace, n�hodn�
  �e�en� s pravd�podobnostmi z�skan�mi z relaxace.
Formulov�no tvrzen� pro postup II a tvrzen� pro maximum z �e�en�
  z�skan�ch postupem I a II.

============================  17.3.2005  ===============================

D�kaz aproxima�n�ho faktoru 4/3 pro kombinaci postupu I a II
n�hodn�ho generov�n� ohodnocen� pro MAX-SAT.

============================  31.3.2005  ===============================

Zopakov�n� a oprava v�po�tu aprox. faktoru Goemans-Williamsonova
algoritmu pro MAX-CUT.
Derandomizace postupu II pro MAX-SAT.
D�sledek PCP v�ty pro neaproximovatelnost MAX-SAT.
Neaproximovatelnost maxim�ln� kliky s jak�mkoli konstantn�m faktorem
(nedokon�en d�kaz max-klika v sou�inu je sou�in max-klik).

============================  7.4.2005  ===============================

Dokon�en� neaproximovatelnosti kliky (omega(sou�in G_i) = sou�in omega(G_i)).
Grupa, t�leso, t�leso Z_p, vektorov� prostor.
Syst�m gener�tor�, dimenze, z�vislost vektor�, b�ze.
V�echny b�ze kone�n� generovan�ho vektorov�ho prostoru maj� stejnou velikost.

============================  14.4.2005  ===============================

Line�rn� zobrazen� (v u���m smyslu) je definov�no podm�nkami g(x+y)=g(x)+g(y) a g(ax)=ag(x).
Line�rn� funkce (v �ir��m smyslu) je takov� f, �e f(x+y)-f(x) nez�vis� na x a je line�rn�m
zobrazen�m od y.
Maticov� tvar line�rn�ho zobrazen� p�i dan� b�zi.
Obraz a j�dro line�rn�ho zobrazen� g:U -> V jsou vektorov� podprostory.
V�ta (bez d�kazu): dim(obraz g) + dim(j�dro g) = dim(U)
D�sledek: dimenze prostoru �e�en� soustavy k nez�visl�ch homogenn�ch rovnic n prom�nn�ch je n-k.
Odstup�ovan� matice.
Nedopo��t�n p��klad soustavy vynucuj�c�, �e sou�et ka�d�ch t�� cyklicky po sob�
jdouc�ch sou�adnic ze 6 v GF(2) je 0.

============================  21.4.2005  ===============================

Do�e�en� p��kladu x_i = x_{i-1} + x_{i-2} pro cyklus d�lky 6 a 5.
Line�rn� funkce nad {0,1}, Hammingovsk� vzd�lenost, roz�i�itelnost z nejv��e 3 bod�,
existence neroz�i�iteln�ch hodnot na n�kter�ch �tve�ic�ch.
K�d pro opravu chyb, minim�ln� vzd�lenost, paritn� k�d, maticov� k�d.

============================  5.5.2005  ===============================

Test n�hodn� �tve�ice: pro n�hodn� y,x_1,x_2 ov��it f(x_1 + y) + f(x_1) = f(x_2 + y) + f(x_2).
P�edpokl�d�me, �e funkce f spln� test n�hodn� �tve�ice s pravd�podobnost� alespo� 1-eps.
Chceme dok�zat, �e pak je bl�zk� n�jak� line�rn� funkci ve smyslu Hammingovsk� vzd�lenosti.
Definice 1. g(y) = Pr_x(f(x+y) + f(x) = 1).
Lemma 1. Pr_x(g(x) \in (t,1-t)) \le eps/(2*t*(1-t)).
Lemma 2. eps/(2*t*(1-t)) < 1/2 => pro ka�d� x g(x) \not\in (2*t,1-2*t).
Jestli�e eps<1/4, definujeme g^*(x) = if g(x) \le 2*t then 0 else if g(x) \ge 1-2*t then 1.
Lemma 3. t < 1/6 => g^*(x) je line�rn� Booleovsk� funkce.
Definice 2. f'(x) = f(x) + g^*(x).
Lemma 4. Pr_x(f'(x+y) = f'(x)) > 1-2*t.
Stru�n� d�kaz. f'(x+y) + f'(x) = f(x+y) + f(x) + g^*(x). Nav�c, vzhledem k definici
g^*(x) plat�, �e Pr_x(f(x+y) + f(x) = g^*(x)) \ge 1-2*t.

============================  12.5.2005  ===============================

Lemma 5. Pokud delta*(1-delta) \ge t, pak existuje c \in {0,1} tak, �e
  (i) Pr(f'(x) = c) \ge 1 - delta
 (ii) Pr(f'(x) \not= c) \le delta
(iii) rho(f',c) \le delta * 2^n
Lemma 6. rho(f,g^* + c) \le delta * 2^n
V�ta (shrnut� pravd�podobnostn�ho testu linearity):
Pokud delta*(1-delta) < 1/6 a eps < delta*(1-delta)*(1-delta*(1-delta)),
pak pro ka�dou Booleovskou funkci f plat� alespo� jedno z tvrzen�:
 (i) Pravd�podobnost nalezen� chyby proti linearit� p�i testu k n�hodn�ch
     nez�visl�ch �tve�ic je alespo� 1 - (1-eps)^k.
(ii) Existuje line�rn� funkce h tak, �e rho(f,h) \le delta * 2^n.

Definice PCP.

Verifik�tor je deterministick� polynomi�ln� algoritmus R(w,x,y),
kter� dostane na vstupu slovo w, d�kaz x v abeced� {0,1} p��slu�nosti w do L
a vektor n�hodn�ch bit� y. P��stup k bit�m x je p�es p��m� adresov�n�,
tedy lze ��st bity x, kter� maj� exponenci�ln� vzd�lenost od za��tku x.

Def. Pro libovoln� p�irozen� ��sla r,s �ekneme, �e L \in PCP(r,s),
pokud existuje verifik�tor R, kter� z y p�e�te nejv��e r bit�,
z x p�e�te nejv��e s bit� a kter� spl�uje pro ka�d� w tyto implikace:
 (i) w \in L => existuje x tak, �e pro ka�d� y je R(w,x,y) = 1.
(ii) w \not\in L => pro ka�d� x je Pr(R(w,x,y)=1) \le 1/2.