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.