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.