Matematika | Felsőoktatás » Varga Dániel - Algebrai módszerek a Boole-hálózatok elméletében

Algebrai mdszerek a Boole-hlzatok elmletben Szakdolgozat rta: Tmavezet: Varga Dniel Friedl Katalin 1996. Tartalomjegyzk 1. Bevezets : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2. A Boole-hlzatok bonyolultsgelmletnek alapfogalmai 2.1 2.2 2.3 2.4 2.5 2.6 Jellsek . Boole-hl zat, Elemi Boole-f ggvnyek A Boole-hl zatok mrtkei . F ggvnysorozatok, Hl zat-sorozatok Bonyolultsgi osztlyok . Trtneti kitekints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3. A polinomilis mdszer els alkalmazsa : : : : : : : : : : : 3 4 4 5 7 7 8 8 9 3.1 Approximci vges test felett 11 3.2 AND approximlsa 13 3.3 Boole-hl zatb l polinom 15 4. A Fourier-appartus : : : : : : : : : : : : : : : : : : : : : : : : 17 4.1 4.2 4.3 4.4 4.5

Multilineris polinomok, Fourier-transzformci Ers s gyenge eljelreprezentci . Motivci : a perceptronok . Bruck lemmja . Alkalmazs: PT1 ( LT2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 21 22 23 25 5. El jelreprezentci s approximci : : : : : : : : : : : : : : 29 5.1 5.2 5.3 5.4 Az Alternatvattel s kvetkezmnyei . Approximci a val sok felett . AND approximlsa . Boole-hl zatb l polinom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 32 34 36 6. "-kzelts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 6.1 A Szimmetrizci s Lemma 40 6.2 Becsls az OR f ggvnyre 42 7. "-kzelts adott spektrltartval : : : : : : : : : : : : : : : : 44 7.1 Alternatvattel az "-kzeltsrl 44 7.2 Az

Alternatvattel alkalmazsa 48 8. Kzelts racionlis trtfggvnyekkel : : : : : : : : : : : : : 50 8.1 Kockaszeletels 51 8.2 THR kzeltse trtf ggvnnyel 53 8.3 THR-hl zatb l trtf ggvny 54 1 9. Interpolci analitikus fggvnyekkel : : : : : : : : : : : : : 55 9.1 A dierencildimenzi 55 9.2 SY MM -hl zatb l analitikus f ggvny 57 10.Ksznetnyilvnts : : : : : : : : : : : : : : : : : : : : : : : : 58 2 1. Bevezets Dolgozatunkban bonyolultsgelmleti als becslseket ad m dszereket mutatunk be k lnbz Boole-hl zati modellekre. Ezen m dszerek bonyolultsgelmleti szempontb l kzs gykerek, de meglepen vltozatosak az alkalmazott klasszikus matematikai appartust tekintve Bizonytsainkban felhasznljuk tbbek kztt a lineris algebra, a lineris egyenltlensgrendszerek elmlete, az approximci elmlet, a racionlis trtf ggvnyek approximci

elmlete s a klasszikus tbbvltoz s analzis egyes alapvet eredmnyeit. A 2. Fejezetben ttekintj k a Boole-hl zatok bonyolultsgelmletnek legalapvetbb fogalmait. A 3. Fejezetben ismertetj k a dolgozatunk f trgyt kpez algebrai m dszercsald els s mig leggfontosabb alkalmazst, Smolensky ttelt a konstans mlysg, szubexponencilis mret Boole-hl zatokr l Smo]. A 4. Fejezetben bemutatjuk a diszkrt Fourier-transzformci s technikt, amely az 5., 6 s 7 fejezetben alapvet segdeszkz nk lesz Illusztrci knt bizonytjuk Bruck ttelt Bru]. Az 5. Fejezetben ismertetj k Aspnes, Beigel, Furst s Rudich ttelt ABFR], amely mind a bizonyts technikjt, mind az eredmnyt tekintve Smolensky ttelnek val s szmtest feletti analogonja. A 6. Fejezetben az "-kzelts fogalmt vizsgljuk Egy n-vltoz s polinom akkor "-kzelt egy Boole-f ggvnyt, ha a Boole-f ggvny rtelmezsi tartomnyn legfeljebb "-nal trnek el. Nisan s Szegedy NS] nyomn als

becslst adunk a logikai V agy f ggvnyt "-kzelt polinomok fokszmra. A bizonyts approximci elmleti technikkon alapul. A 7. Fejezet a szerz nnll eredmnyeit tartalmazza az "-kzeltsrl A Farkas Lemma felhasznlsval sz ksges s elgsges felttelt adunk egy Boole-f ggvny adott fokszm polinommal val "-kzelthetsgre. Megmutatjuk, hogy ez az ereddmny specilis esetknt tartalmazza Aspnes et al. 5 Fejezetben trgyalt Alternatvattelt K s Gza eredmnyre K s] tmaszkodva valamelyest megjavtjuk a Nisan s Szegedy ttelben szerepl konstansokat. A bizonyts szemben Nisan s Szegedy bizonytsval teljesen elemi konstrukci n alapul. A 8. Fejezetben Paturi s Saks PS] nyomn a paritsf ggvnyt szmt 2 mlysg THR-hl zatokat vizsgljuk. Ennek kapcsn bemutatunk egy rokon elemi geometriai problmt, s az azzal kapcsolatos legfontosabb eredmnyeket. A THR-hl zatok vizsglatra ezutn bevezetj k s alkalmazzuk a racionlis trtf ggvnyekkel val

kzelts m szert. A 9. Fejezetben Smolensky ttelt Smo] ismertetj k szimmetrikus kapukat hasznl hl zatok szmtsi erejrl A bizonyts sorn az elemi 3 tbbvltoz s analzis m dszereit hasznljuk, a Boole-f ggvnyt interpoll analitikus f ggvnyek k-adrend parcilis derivltjait vizsglva. 2. A Boole-hlzatok bonyolultsgelmletnek alapfogalmai 2.1 Jellsek Bevezet nk nhny jellst, amelyek a kombinatorikban s a bonyolultsgelmletben standardnak tekinthetk. n] := f1 ::: ng 2X jelli X hatvnyhalmazt ;X  jelli X sszes k-elem halmazainak halmazt ; Xk  jelli X sszes legfeljebb k-elem halmazainak halmazt ; nk := P ;n = ; n] i2k] i k k A bonyolultsgelmletben a kvantitatv eredmnyeket hagyomnyosan ord -jellsek hasznlatval adjk meg, hiszen a bonyolultsgi mrtkek nagysgrendje legtbbszr lnyegesebb, mint az egzakt rtk k. Emlkeztet l: 2.1 Denci f (n) = O(g(n)) azt jelenti, hogy ltezik olyan c 2 R  c > 0, hogy jf (n)j 

 cjg (n)j minden n-re. f (n) = o(g(n)) azt jelenti, hogy minden c 2 R  c > 0 szmhoz ltezik olyan m 2 N , hogy minden n  m-re jf (n)j < cjg(n)j. f (n) = (g(n)) azt jelenti, hogy ltezik olyan c 2 R  c > 0, hogy jf (n)j   cjg (n)j minden n-re. f (n) = (g(n)) azt jelenti, hogy f (n) = (g(n)) s f (n) = (g(n)). 4 nnll jellst vezet nk be nhny gyakran elfordul nagysgrendre: const poly(n) lin(n) polylog(n) subexp(n) qpoly(n) := := := := := := O(1) nO(1) O(n) log(n)O(1) 2no 2polylog(n) (= npolylog(n)) (1) A tovbbiakban  hacsak k ln nem jelezz k az ellenkezjt  a dolgozatban szerepl f ggvnysorozatok f gg vltoz ja mindig n, az ppen vizsglt Boole-f ggvny vltoz inak szma. Ezrt, ha ez nem okoz zavart, az n argumentumot nem rjuk ki. 2.2 Boole-hlzat, Elemi Boole-f ggvnyek 2.2 Denci V := f;1 +1g Boole-fggvnynek neveznk egy tetszleges V n ;! V fggvnyt A V n-et nha kocknak, elemeit cs csoknak fogjuk nevezni. Megjegyzs. Ezen denci

mellett a +1 a hagyomnyosan hasznlt Igaz s a ;1 a Hamis logikai rtknek felel meg. A Boole-hl zat legltalnosabb denci ja a kvetkez: 2.3 Denci Boole-hlzatnak neveznk egy aciklikus irny tott gr- fot, amelynek nem forrs cs csai Boole-fggvnyekkel vannak c mkzve, mghozz gy, hogy a cs csba men lek azonos tva vannak a Boole-fggvny vltoz ival. A nem forrs cs csokat kapuknak nevezzk Feltesszk, hogy a hl zatnak csak egy nyelje van. A hl zat forrsait bemeneteknek, nyeljt kimenetnek nevezzk. A hl zat ltal kiszm tott fggvny rtelemszer en, rekurz ve de nil dik a bemenetektl a kimenetig Egy kapu bemenetei azok a kapuk, amelyekbl l indul az adott a kapuba. A kapu sei az sszes kapuk, melyekbl az adott kapu elrhet irny tott ton. Mint ltjuk, a Boole-hl zat minden cscsa, s a hl zat maga is egy-egy Boole-f ggvnyt szmt. 2.4 Denci A hl zat k-dik szintje azon kapuk halmaza, amelyek minden sktl legfeljebb k tvolsgra vannak, de van

olyan sk, amelytl pontosan k tvolsgra vannak. Szintezettnek nevezzk a hl zatot, ha csak egyms utni szintek kztt megy l benne. 5 Ha a kimenet kiszmtst idbeli folyamatnak tekintj k, akkor a k-dik szint azokb l a kapukb l ll, amelyek a szmts k-dik fzisban szmtjk ki a kimenet ket. 2.5 Denci Topologikus sorrendnek nevezzk a kapuk egy tetsz- leges felsorolst, amely kompatibilis a hl zat grfjval, teht amelyben minden kaput megelznek az sei. A Boole-hl zat denci ja megengedi a kapukban tetszleges Boolef ggvnyek hasznlatt. Bonyolultsgelmleti szempontb l az rdekes helyzet az, ha a cscsokban nem enged nk meg akrmilyen f ggvnyt, csak valamilyen rtelemben egyszereket Att l f ggen, hogy milyen f ggvnyeket enged nk meg, k lnfle hl zatosztlyokhoz juthatunk. Megjegyzs. Egy olyan f ggvny, mint pldul az AND, val jban f ggvnyek csaldjt jelenti, hiszen AND van ktvltoz s, hromvltoz s 2.6 Denci A leggyakrabban hasznlt

Boole-fggvnyek: AND: OR: MAJ : MODm: EXACTk : PAR: +1, ha minden bemenet +1, ;1 egybknt. ;1, ha minden bemenet ;1, +1 egybknt. +1, ha a bemenetek legalbb fele +1, ;1 egybknt. +1, ha az egyesek szma oszthat m-mel, ;1 egybknt. +1, ha az egyesek szma pontosan k, ;1 egybknt. a bemenetek szorzata. Ez egy 1 szorz t l eltekintve ppen MOD2. Az eddig emltettek mind szimmetrikus Boole-f ggvnyek, teht a kimenet csak a bemenenet egyeseinek szmt l f gg. A szimmetrikus Boolef ggvnyek csaldjt SY MM -mel jellj k THR: (lineris k szbf ggvny) A MAJ ltalnostsa. A bemenetek valamely lineris kombinci jb l kivon egy k szbrtket, s pontosan akkor ad 1-et, ha az eredmny nemnegatv. 2.7 Denci Ha GATE1 GATE2 ::: Boole-fggvny-osztlyok, akkor fGATE1  GATE2  :::g-hlzatnak nevezzk azon Boole-hl zatok osztlyt, amelyeknek a kapui ezen Boole-fggvny-osztlyok elemei. Pldul fAND NOT g-hl zat azon Boole-hl zatok sszessgt jelenti, amelyeknek kapui kizr

lag AND s NOT f ggvnyeket szmtanak. 6 2.3 A Boole-hlzatok mrtkei 2.8 Denci A hl zat mrete a kapuk szma, A hl zat mlysge a szintek szma. A befok a maximlis befok a hl zat grfjnak cs csain. A rend a maximlis befok az els szint kapuk kztt. Ha feltessz k, hogy a THR-f ggvny k szbrtke s bemeneteinek slyai egsz szmok, az ugyan nem vltoztat a THR f ggvnyosztlyon, de ekkor vizsglhatjuk a kapu egy rdekes mrtkt: 2.9 Denci Egy THR-kapu slya az egytthat k (belertve a kszbrtket) abszol trtk-sszege A Boole-hl zat denci jban megengedt k a prhuzamos leket is. Ezekre a gyakorlatban azrt nincs sz ksg, mert az ptelemknt hasznlt f ggvnyek szmtsi kpessgt ez ltalban nem nveli. Pldul egy AND kapuba fut prhuzamos lek egyszeren egy kivtelvel elhagyhat k, s egy PAR kapuba fut prhuzamos lek esetben csak a darabszmuk paritsa szmt. Ms a helyzet a MAJ kapukkal. Ha modell nkben MAJ kapukat hasznlunk, s nem tesz nk

megktst a prhuzamos lekrl, akkor knnyen modellezhetj k az ltalnos THR-f ggvnyt egyetlen MAJ -kapuval. Ezrt MAJ -kapukat hasznl modellekben hasznos mrtk a grf leinek szma. Ezt szoktk a hl zat lkomplexitsnak nevezni. A prhuzamos leket hasznl MAJ kapur l THR kapukra ttrve ez lnyegben ppen a hl zat THR-kapuinak sszslya, amit a THR-hl zat slynak nevez nk. 2.4 F ggvnysorozatok, Hlzat-sorozatok 2.10 Denci Boole-fggvny-sorozatnak nevezznk egy ffni : i 2 N g sorozatot, ha fni egy ni -vltoz s Boole-fggvny, s fnig termszetes szmok egy szigor an monoton nv sorozata. 2.11 Denci Hlzat-sorozatnak neveznk egy fHni : i 2 N g sorozatot, ha Hni egy ni bemenet hl zat, s fnig termszetes szmok egy szigor an monoton nv sorozata. rtelemszer m don a hl zatsorozat akkor szmtja a fggvnysorozatot, ha minden i-re Hni kimenete fni . 7 2.5 Bonyolultsgi osztlyok Tekints nk egy modellt, egy vagy tbb mrtkkel. Ha a mrtkekre valamilyen

fels korltokat kvetel nk meg, ahol a fels korlt lehet akr egzakt (pldul 3 mlysg hl zat), akr nagysgrendi (pldul qpoly mret hl zat), akkor hlzat-osztlyt deniltunk. Felhvjuk a gyelmet arra, hogy a hl zat-osztly nevvel ellenttben nem hl zatok, hanem hl zat-sorozatok halmaza. A hl zat-osztly denilsa utn denilhatjuk a megfelel nyelvosztlyt, azon nyelvek halmazt, amelyeket a hl zat-osztly valamely eleme szmt. A klasszikus nyelvosztly, AC 0, a konstans mlysg, polinom mret fAND OR NOT g-hl zatokkal szmthat nyelvek osztlya jells nkkel gy fest: 2.12 Denci AC 0 := (fAND OR NOT g-hl zat,poly mret, const mlysg) Ha kicsit pongyoln pldul azt rjuk, hogy SY MM  AC 0, az alatt azt rtj k, hogy SY MM f ggvnyekbl alkotott tetszleges f ggvnysorozat szmthat AC 0-ban. Plda. Ksbb tallkozni fogunk tbbek kzt a kvetkez hl zatosztlyokkal: (fAND OR NOT MOD3g-hl zat, k mlysg, 2o(n = k ) ) (THR-hl zat,poly sly, 2

mlysg, lin mret) (SY MM -hl zat,m(n) befok, k(n) mret) 1 2 2.6 Trtneti kitekints A konstans mlysg, polinom mret Boole-hl zatok vizsglatt FurstSaxe-Sipser FSS], s Ajtai Aj] kezdemnyezte. 1981-ben egymst l f ggetlen l belttk, hogy a 212-ban denilt AC 0 hl zatok nem kpesek a paritsf ggvny kiszmtsra. 2.13 Ttel (Furst-Saxe-Sipser,Ajtai) PAR 62 AC 0 A ttel vgs vltozata Yao Y] s H stad Ha] munkja: 2.14 Ttel (Yao,Hstad) PAR 62 (fAND OR NOT g;hl zat d mlysg 2o(n = d )) 1 ( +1) 8 Egyszer konstrukci mutatja, hogy ez az eredmny konstansokt l eltekintve les. Furst et al., Ajtai, Yao s Hastad bizonytsai nem algebrai, hanem val sznsgszmtsi technikkon alapulnak, ezrt dolgozatunkban nem trgyaljuk azokat, de az 213 Ttelre kt polinomilis m dszert alkalmaz bizonytst is adunk majd Az egyik Smolensky Smo], a msik Aspnes et al ABFR] eredmnye. Br dolgozatunkban nem trgyaljuk, mindenkppen emltst rdemel, hogy mint arra

mr Furst-Saxe-Sipser rmutatott, a konstans mlysg hl zatokra vonatkoz als becslsek lefordthat k a bonyolultsgelmlet egy msik gnak, az orkulumos Turing-gpek elmletnek nyelvezetre, s ott rtkes eredmnyeket adnak. Lsd pldul KVVY]Bei2] 3. A polinomilis mdszer els alkalmazsa Ebben a fejezetben Smolensky Smo] nyomn bizonytjuk Yao s H stad ttelnek egy valamivel gyengbb konstansokat ad , de ltalnosabb vltozatt. Egyelre csak kimondjuk a ttelt. 3.1 Ttel (Smolensky) PAR 62 (fAND OR NOT MOD3g;hl zat k mlysg 2o(n = k ) ). 1 2 Most lssunk egy nav ksrletet Furst et al. eredeti lltsnak bizonytsra a polinomok alkalmazsval: Az egyszerbb trgyals kedvrt az OR-kapukat a De Morgan-szably szerint lecserlj k AND-ekre s NOT -okra. Lthat , hogy ez legfeljebb hromszorozza a kapuk szmt, ami eredmnyeinket nem rinti 3.2 llts A 2 Qi2n] (xi + 1)=2 ; 1 polinom n-edfok , s a V n halmazra megszor tva ppen az AND Boole-fggvnnyel

egyenl. 2 A hl zathoz rendelt polinomot a bemenetektl a kimenet fel induktve deniljuk, a hl zat egy topologikus sorrendje szerint haladva vgig a kapukon. A i bemenet polinomja legyen az xi polinom Ha egy NOT -kapu bemenetnek a p polinom felel meg, akkor a kimenetnek feleltess k meg a ;p polinomot. Ha egy AND-kapu bemeneteinek a p1  p2 ::: pQ m polinomokat feleltett k meg, akkor a kimenetnek feleltess k meg a fenti 2 i2m] (pi + 1)=2; ; 1 polinomot. Vegy k szre, hogy ez a polinom V n -re megszortva ppen a megfelel AND-kapu kimenett adja. Az eljrst az sszes kapura elvgezve elrj k, hogy az n bemenettel rendelkez hl zathoz hozzrendelt 9 n-vltoz s polinom V n-re megszortva pontosan a hl zat ltal szmtott Boole-f ggvnyt adja meg. Ha ezek utn a konstrult polinom fokszmt fel lrl tudjuk becs lni a hl zat mretnek s mlysgnek valamilyen f ggvnyvel, s van als becsls nk arra, hogy hanyadfok polinommal lehet interpollni a szmtand Boole-f

ggvnyt, akkor als becslst nyert nk a f ggvnyt szmt Boolehl zat mretre. Sajnos ezt az gretes program nem vezet eredmnyre. Ha ugyanis valamelyik kapu bemeneteinek szma n-nl nagyobb, akkor a hozzrendelt polinom fokszma azonnal n fl n, s a becsls triviliss vlik, hiszen  mint hamarosan ltni fogjuk  minden Boole-f ggvny interpollhat legfeljebb n-edfok polinommal. Razborov Ra] 1985-s cikkben megmenti az tletet. (Br  eredmnyt egy msik formalizmusban, a mtrixalgebrk nyelvn fogalmazta meg) Razborov j gondolata a kvetkez: Eset nkben a kapu kimenett pontosan tudtuk reprezentlni a bemeneteket reprezentl polinomok polinomjval, de ezen lps sorn a fokszm kezelhetetlen l ntt. Azonban lehetsges a kimenet reprezentlsa sokkal kisebb fokszm polinomjval is a bemeneti polinomoknak, ha megengedj k, hogy a kimenet nhny  kevs  bemenetre hibs legyen. Ez esetben olyan als becslsre van sz ksg, amely azt szavatolja, hogy a krdses f ggvny nem

lehet sok helyen egyenl egy kis fokszm polinommal. Smolensky Smo] volt az, aki Razborov bizonytst az ltalunk is hasznlt nyelven jrafogalmazta s nmileg tovbbfejlesztette. Razborov egy msik jelents eredmnye als becsls a klikkf ggvnyt szmol fAND ORg-hl zat mretre Ra2]. Ez a bizonyts szintn azon alapul, hogy a kapu kimenett kzeltj k egy olyan f ggvnnyel, amelynek bizonyos kombinatorikai paramterei j l becs lhetk Karchmer Kar] szrevette, hogy tbb ilyen jelleg bizonyts mgtt kzs kombinatorikai jelensg hz dik meg, s az approximci s techniknak megfogalmazta a legltalnosabb kerett. Ezt Karchmer s Wigderson Wig] fzi s m dszernek nevezte el. A fzi s m dszer segtsgvel a dinamikus bonyolultsgi krdseket tfogalmazhatjuk statikus krdsekk  bizonyos nagy halmazrendszerek lefogsi problmiv. Sajnlatos, de nem meglep m don a kapott kombinatorikai problmk az esetek tbbsgben ppen gy kezelhetetlennek bizonyulnak, mint az eredeti

bonyoluultsgelmleti krdsek. 10 3.1 Approximci vges test felett A tovbbiakban p rgztett pratlan prmszm, s Zp a p-elem test. A Boole-f ggvnyek tovbbra is V n ! V f ggvnyek, de V -t most Zp rsznek tekintj k. 3.3 Denci Legyen S  Znp Legyen f S -rl Zp-be kpez fggvny, s r valamilyen S  S 0  Znp halmazr l Zp-be kpez fggvny. Azt mondjuk, hogy r S felett reprezentlja f -et, ha S -re megszor tva f s r azonosan egyenlek. 3.4 Denci Ha f a V n kockn van rtelmezve, s r V n felett reprezentlja, akkor egyszer en azt mondjuk, hogy r reprezentlja f -et Ennek a reprezentci nak van egy fontos tulajdonsga, amit a ksbbiekben (a val s szmtest esetn) a 4. Fejezetben rszletesen fogunk tanulmnyozni, de most csak kimondunk s bizonytunk 3.5 Denci Egy n-vltoz s polinomot multilinerisnak neveznk, ha minden vltoz jban lineris. 3.6 Denci Multilinearizlsnak nevezzk azt a m veletet, amikor egy tbbvltoz s polinom monomjaiban a pros

kitevket 0-ra, a pratlanokat 1-re cserljk. Lthat , hogy p multilinearizltja V n-en azonosan egyenl p-vel, hiszen 1 s ;1 hatvnyai csak a kitev paritst l f ggenek. 3.7 llts Minden V n-rl Zp-be kpez fggvny  specilisan minden Boole-fggvny  egyrtelm en reprezentlhat multilineris polinommal. Bizonyts. Egzisztencia: f -hez elszr interpolci val tallhatunk egy reprezentl polinomot, ami nem felttlen l multilineris. Ennek a multilinearizltja bizonytja a ltezst Unicits: Ltezsi eredmny nket gy is fogalmazhatjuk, hogy a multilineQ ris monomok (azaz a j2J xj alak f ggvnyek) generljk a V n-rl Zp-be men f ggvnyek 2n-dimenzi s vektortert. A multilineris monomok szma 2n, hiszen n] minden rszhalmazhoz egyrtelmen tartozik multilineris monom. Mivel a monomok generljk a vektorteret, s darabszmuk ppen a vektortr dimenzi ja, ezrt f ggetlenek is, amibl pedig mr kvetkezik az egyrtelmsg. 2 11 3.8 Denci Egy f Boole-fggvnyt egy

r : V n ! Zp fggvny " hibval approximl, ha legfeljebb 2n" darab cs cs kivtelvel megegyeznek a V n kockn. Smolensky eredmnye szerint ha f kis fokszm polinom Zp felett, akQ kor a PAR = j2n] xj Boole-f ggvnyt nem approximlhatja kis hibval. Pontosabban: 3.9 p Ttel. (Smolensky) Ha a Zp feletti n-vltoz s r polinom fokszma n, akkor r PAR-t (1) hibval approximlja. Bizonyts. p Tegy k fel, hogy a n fok r polinom az S  V n halmaz felett reprezentlja a x1 x2 xn f ggvnyt. Az S -bl Zp-be kpez f ggvnyek Zp feletti jS j dimenzi s vektorteret alkotnak. Clunk, hogy ezeket a f ggvnyeket n=2 + p + n fok polinomokkal reprezentljuk S felett. Elszr vlasszunk egy tetszleges multilineris reprezentci t. Ezt megtehetj k a 37 "llts szerint, hiszen S  V n Ezt a reprezentl polinomot fogjuk m dostani, minden monomjt k ln-k ln. Ha egy monom n=2-nl nem nagyobb fok, ne vltoztassuk meg. Legyen az m monom n=2-nl nagyobb fok, azaz valamilyen jJ j >

n=2-re m(x) = Y j 2J xj = x1 x2 Ez ut bbi az x 2 S pontokon ppen Y r(x) j 62J xn Y j 62J x;j 1 xj : p Ez egy legfeljebb n=2+ n fok polinom. Ezt a helyettestst minden n=2-nl nagyobb fok monomra elvgezve tetszleges S -bl Zp-be kpez f ggvny reprezentlhat a kvnt fok polinommal. Mint mr korbban lttuk, a ;  n monomok linerisan f ggetlenek. A d-fok monomok szma;ppen d . E  n szerint a d-nl nem nagyobb fok polinomok egy Zp feletti d -dimenzi s vektorteret alkotnak. Teht   np : jS j  n 2+ n A ttel ezutn kvetkezik az albbi ismert becslsbl. 3.10 Lemma (Cherno-korlt)   1 n  e;k =2n n 2  n;2 k 12 2 2 3.2 AND approximlsa Ezen alfejezet eredmnyeit a trgyals egyszerstse vgett a hromelem test felett mondjuk ki, br kis vltoztatssal minden Zp test felett is rvnyesek. Emlkeztet nk r, hogy AND az a Boole-f ggvny, amely 1, ha minden vltoz 1, s ;1 egybknt. Most beltjuk, hogy az AND Boolef ggvny approximlhat kis

fokszm polionommal, nem tl nagy hibval A gyelmes olvas szreveheti, hogy ez az llts ebben a formban rdektelen, hiszen az azonosan ;1 nulladfok polinom 21n hibval approximlja AND-et, s ennl jobb eredmny nem is vrhat . Hogy lltsunkat pontoss s persze a ksbbiekben alkalmazhat v tegy k, kiterjesztj k az approximci denci jt. 3.11 Denci Legyen  val sz n sgeloszls a V n halmazon f legyen a szoksos m don a kockr l Zp-be kpez fggvny, s r n-vltoz s polinom. Azt mondjuk, hogy r az f -et " hibval approximlja a  bemeneti eloszls mellett, ha Pr (f (x) 6= r(x))  " Lthat , hogy eredeti approximci -fogalmunk ennek az a specilis esete, amikor -nek az egyeletes eloszlst vlasztjuk. 3.12 Ttel (Smolensky) Legyen l pozit v egsz, s  tetszleges val sz n sgeloszls V n-en Ekkor ltezik Z3 feletti 2l-fok polinom, amely 1=2l hibval approximlja az n-vltoz s AND-fggvnyt a  bemeneti eloszls mellett. Bizonyts. A konstrukci

alapgondolata azonos az albbi gyakan hasz- nlt tlettel: (Kommunikci s bonyolultsgelmleti alkalmazsra j plda Nis]): Egy vges test feletti x vektorr l kell eldnten nk, hogy az azonosan 0 vektor-e. Megengedett megkrdezn nk a skalrszorzatt egy tetszleges ltalunk adott vektorral. Algoritmusunk: Ellltunk l darab egymst l f ggetlen vletlen 1-vektort, s mindegyiket skalrszorozzuk x-szel Ha van nemnulla skalrszorzat, akkor x nemnulla. Ha minden skalrszorzat nulla, akkor legfeljebb 1=2l tvedsi val sznsg mellett kijelenthetj k, hogy x = = 0. Vlasszuk ki n] egy J vletlen rszhalmazt, minden rszhalmazt egyforma val sznsggel vlasztva. Tekints k az 13 sJ (x) := X j 2J !2 (xj ; 1) +1 msodfok polinomot. 3.13 Lemma Ha x = (1 1 ::: 1), akkor Pr(sJ (x) = 1) = 1 Ha x 6= 6= (1 1 ::: 1), akkor Pr(sJ (x) = ;1)  12 (a val sz n sget J vletlen vlasztsra nzve tekintjk) A Lemma bizonytsa. Az llts els rsze trivilis A msodik rsz

bizonytshoz rgzts nk egy x nem azonosan 1 bemenetetPNevezz nk jnak egy J halmazt, ha sJ (x) = ;1. J pontosan akkor j , ha j2J (xj ; 1) 6= 0 Kt esetetPk lnbztet nk meg x vlasztsa szerint. I. eset: j2n](xj ; 1) 6= 0 "lltsuk prba a J halmazokat gy, hogy mindegyik ker ljn prba a komplementervel. X X j 2J j 2n]nJ (xj ; 1) + (xj ; 1) 6= 0 ezrt J s n] n J kz l legalbb az egyik j . Ezzel az lltst az Iesetre belttuk. P II. eset: j2n](xj ; 1) = 0 Feltett k, hogy x nem csupa-1 vektor, legyen mondjuk xn = ;1. X (xj ; 1) = ;1 j 2n;1] Az I. esethez hasonl an lltsuk prba n ; 1] rszhalmazait, s jegyezz k meg, hogy melyek a j halmazok. Most minden rszhalmazhoz vegy k hozz az n elemet. A rszhalmazhoz tartoz sszeg ezltal xn ; 1 = 1-gyel n Az eredetileg j halmazokb l, amelyekre az sszeg nemnulla volt, ennek hatsra lehet j is, rossz is. Ellenben az eredetileg rossz halmazokb l, amelyekre az sszeg nulla volt, biztosan j keletkezik. #gy most is

legalbb annyi j halmaz van, mint rossz. 2 A Ttel bizonytsa Lttuk, hogy egy vletlenszeren vlasztott sJ m- sodfok polinom legalbb 1=2 esllyel egyenl AND(x)-szel minden x x-re. A hibt ismtlssel cskkentj k. Legyen fJi : i 2 l]g egymst l f ggetlen l vlasztott vletlen rszhalmazok csaldja. Tekints k a 14 Y i2l] (sJi + 1) ; 1 2l fok polinomot. Ez ppen az AND(sJ  sJ  ::: sJl ) Boole-f ggvnyt reprezentlja A lemmb l azonnal kvetkezik, hogy ez a val sznsgi vltoz polinom minden x bemenetre legfeljebb 1=2l val sznsggel hibzik Van teht egy polinomcsaldunk, amely csupa 2l fok polinomb l ll, s minden x-re legalbb az (1 ; 1=2l )-edrsz k j l reprezentlja AND-et az adott xen. A ttel bizonytshoz mr csak egy ketts leszmllst kell alkalmazni Ebbl kvetkezik, hogy van olyan eleme a polinomcsaldnak, amely a  bemeneti eloszls mellett (1 ; 1=2l) val sznsggel egyenl AND-del. Ezzel az lltst bizonytottuk. 2 1 2 3.3 Boole-hlzatbl

polinom Az AND-re vonatkoz approximci birtokban megadunk egy eljrst, amely egy k mlysg, S mret fAND OR NOT MOD3g -hl zathoz konstrul egy kis fokszm polinomot, amely approximlja a hl zat ltal szmtott f ggvnyt. Els lpsknt a deMorgan-szably alkalmazsval az OR-kapukat lecserlj k AND s NOT kapukra. Ez a hl zat mrett legfeljebb meghromszorozza A hl zatot a bemenetektl a kimenetek fel haladva topologikus sorrendben (2.4 Denci ) kapunknt alaktjuk polinomm Kezdlpsknt az xi bemeneteket az xi polinomokkal reprezentljuk. (i 2 n]) A rekurzi sorn folyamatosan fenntartjuk az approximl polinomoknak azt a tulajdonsgt, hogy minden x 2 V n bemeneten V -beli rtket adnak. Ha egy kapu sorra ker l, akkor a topologikus sorrend denci ja szerint a bemeneteire mr megadtuk az approximl polinomokat. Legyenek ezek g1(x) g2(x) ::: gm (x). Hrom esetet k lnbztet nk meg aszerint, hogy milyen kapur l van sz I. eset: NOT -kapu A kimenet ekkor 0 hibval

reprezentlhat a ;g1 polinommal, amely a bemenet elsfok polinomja. II. eset: MOD3-kapu A kimenet szintn 0 hibval reprezentlhat a 0 12 X @ (gi + 1)2A + 1 i2m] 15 negyedfok polinommal. Ugyanis (gi + 1)2 akkor 1, ha gi = 1, s akkor 0, ha gi = ;1. Az sszeg eszerint pontosan akkor 0, ha az 1 rtk gi-k szma hrommal oszthat . III. eset: AND-kapu A hl zat bemeneteinek V n halmazn vett egyenletes eloszls indukl egy  eloszlst a (g1(x) g2(x) ::: gm (x)) vektorra nzve. Plda. g1(x1  x2 x3 ) := (x1 + 1)(x2 + 1) ; 1 (= OR(x1 x2 )) g2(x1  x2 x3 ) := (x2 + 1)(x3 + 1) ; 1 (= OR(x2 x3 )) Ekkor V 3 egyenletes eloszlsa AND(g1 g2) albbi bemeneti eloszlst induklja: Pr(g1(x) = ;1 g2(x) = ;1) = 1=8 Pr(g1(x) = ;1 g2(x) = +1) = 1=8 Pr(g1(x) = +1 g2(x) = ;1) = 1=8 Pr(g1(x) = +1 g2(x) = +1) = 5=8 Az induklt  eloszlsra alkalmazzuk a 3.12 Ttelt Ez egy olyan h m-vltoz s polinomot ad, amely 1 ; 1=2l -val sznsggel a gi bemenetek AND-f ggvnye lesz.  vlasztsa

s az induklt eloszls denci ja miatt a h(g1(x) :::gm (x)) polinom 1=2l hibval approximlja az AND(g1 (x) :::gm(x)) Boole-f ggvnyt, ha az x-et egyenletes eloszlssal vlasztjuk V n-bl. Ezzel a hrom esetet egyenknt kezelt k. sszefoglalva: a kapu kimenete minden esetben kzelthet a kapu bemeneteinek legfeljebb (2l)-fok polinomjval, gy, hogy a hl zat azon inputjainak arnya, amelyekre ez a kapu hibs eredmnyt ad, legfeljebb 1=2l. A polinomm alaktst az sszes kapura elvgezve egy polinomot kapunk, amely approximlja a hl zat ltal szmtott f ggvnyt. Kt krds maradt: mekkora hibval szmt, s mennyi a fokszma? Mindkt krds egyszeren megvlaszolhat . Az i szinten az elz szintek kapuib l alkotott polinomok legfeljebb (2l)-fok polinomjai szerepelnek #gy a fokszm minden szinten az elz szint maximlis fokszmnak (2l)-dik hatvnyval becs lhet. A teljes fokszm teht legfeljebb (2l)k Minden egyes kapu a bemenetek (nem a sajt bemenetei, hanem az egsz hl

zat bemenetei) legfeljebb 1=2l -ed rszn hibzik. #gy a globlis hiba legfeljebb N=2l . Eddigi eredmnyeinket ttell fogalmazzuk: 16 3.14 Ttel Legyen l 2 N Ha egy fAND OR NOT MOD3g-hl zat mrete N s mlysge k, akkor a hl zat kimenete approximlhat N=2l hibval egy Z3 feletti (2l)k fokszm polinommal. 2 Vlasszuk l-et ( 12 n1=2k )-nak, s alkalmazzuk a ttelt a PAR Boolep f ggvnyt szmt hl zatra. Ekkor a nyert polinom fokszma ppen n, s a ppolinom N=2 n = k hibval approximlja PAR-t. A 39 Ttel szerint egy n fok polinom PAR-t (1) hibval kpes csak approximlni. Teht 1 2 1 2 N = (2 n = k ) s ezzel a 3.1 Ttel bizonytst befejezt k 1 2 1 2 2 4. A Fourier-appartus Az elz fejezetben mr tallkoztunk azzal a gondolattal, hogy egy test felett egy V n-en rtelmezett f ggvny egyrtelmen interpollhat multilineris polinommal (3.7 "llts) Ebben a fejezetben az R test esetben rszletesen vizsgljuk az interpoll polinom tulajdonsgait. 4.1

Multilineris polinomok, Fourier-transzformci A tovbbi fejezetekben a val s szmok teste felett dolgozunk. 4.1 Denci Saks nyomn, nmileg nehzkesen, pszeudo-Boole fggvnynek neveznk egy f fggvnyt, ha a V n kocka cs csaib l a val s szn mokba kpez, azaz ha f 2 R V . A pszeudo-Boole f ggvnyek algebrt alkotnak a val sok felett az elemenknti szorzssal. Ennek az algebrnak termszetes bzist adjk V n egyelem rszhalmazainak karakterisztikus f ggvnyei. A pszeudo-Boole f ggvnyek tern skalrszorzatot denilunk. hf jg i := X x2V n f (x)g(x) 4.2 Denci Egy J  n] halmazra J := Qj2J xj A J fggvnyeket parits- vagy monomfggvnyeknek fogjuk nevezni. 17 Kt, sokat hasznlt tulajdonsguk: J K = J 4K (J 4 K a kt halmaz szimmetrikus dierencija) X 2n J = 0 0 J 6= 0 v Ebbl a kt azonossgb l knnyen levezethet legfontosabb tulajdonsn V guk, hogy ortogonlis bzist alkotjk R -nek a fent bevezetett skalrszorzsra nzve: 4.3 llts J (v) = 2n J = K

0 J= 6 K hJ jK i = Pronknt ortogonlisak, s 2n a darabszmuk, teht bzist alkotnak. #gy minden pszeudo-Boole f ggvny egyrtelmen felrhat X hrjJ i J r = 21n J n] alakban. Ezt nevezz k r spektrlis felrsnak vagy spektrlis alakjnak Bevezetj k a kvetkez jellst: 4.4 Denci Az r 2 R V n fggvnyhez de niljuk az r^ 2 R 2 n fggvnyt:  ] r^(J ) := 21n hrjJ i Az r 7! r^ lekpezs lineris transzformci R V n s R 2 n kztt. Ezt Fouriertranszformcinak nevezzk  ] r= X J n] r^(J )J Dolgozatunk legnagyobb rszt ezen transzformci vizsglatnak, illetve alkalmazsainak szentelj k. A spekrlis felrst mint multilineris polinomot azonostjuk a megfelel r^ f ggvnnyel, gy beszl nk pldul az r-et reprezentl r^ polinomr l. r^-nak, mint polinomnak a szoksos m don deniljuk a fokszmt s srsgt. Formlisan: 18 4.5 Denci r^ foka deg^r = maxfjJ j : r^(J ) 6= 0g r^ srsge dns^r = jfJ : r^(J ) 6= 0gj 4.6 Denci A spektrlis alak egyrtelm

sge miatt egy tetszleges pszeudo-Boole fggvnynek de nilhatjuk a fokszmt s s r sgt, mint a spektrlis fel rsnak fokszmt illetve s r sgt. 4.7 Denci Spektrltartnak nevezzk a spektrlis alak nemnulla egytthat j monomjainak halmazt: S (r) := fJ 2 2n] : r^(J ) 6= 0g 4.8 Denci Legyen S  2n], s r 2 R V n r spektrlis projekcija S -re az r merleges vet tse a pszeudo-Boole fggvnyek vektorterbl az S tart j pszeudo-Boole fggvnyek alterbe. Azaz X rjS := 21n hrjJ i J J 2S V n -bl Az albbiakban megadjuk a Fourier-transzformci nak mint az R R 2 n -be men lineris transzformci nak a mtrixt. A mtrix sorai az n] rszhalmazaival, oszlopai a V n cscsaival vannak indexelve. Tudjuk, hogy r^(J ) = 21n hrjJ i Ebbl ltszik, hogy a mtrix J -vel indexelt sora ppen az 21n J vektor. #gy a mtrix J -dik sornak v-dik eleme 1 2n J (v ).  ] 4.9 Denci Hn(J )(v) := J (v) v 2 V n J  n] 4.10 llts r^ = 21n Hn r r = HnT r^ Most megadunk egy

megfeleltetst 2n] s V n elemei kztt. 4.11 Denci A K 2 2n] halmazhoz rendeljk a vK 2 V n cs csot: vK k] := ;1 k 2 K 0 k 26 K 19 2 4.12 llts J (vK ) = (;1)jJ K j 2 Ebbl azonnal ltszik, hogy ha a cscsokat is a rszhalmazokkal cmkzz k  ezzel a mtrix sorait s oszlopait megfeleltetve egymsnak , akkor szimmetrikus mtrixot kapunk. Ha a rszhalmazokat lexikograkusan rendezz k, akkor Hn-bl egy hagyomnyosan indexelt 2n 2n-es mtrixot kapunk. Knnyen ellenrizhet, hogy ez az albbi rekurzi val adhat meg H0 := H1 := Hn+1 := 1 1   1 1 ;1 Hn Hn Hn ;Hn  A Hn mtrixokat Sylvester-fle Hadamard mtrixoknak nevezz k. Megjegyzs. Hadamard-mtrixnak az ortogonlis 1-mtrixokat nevezz k Mindez a spektrlis felrs albbi egyszer induktv ellltsnak felel meg. r+(x1  x2  ::: xn;1) := r(x1  x2 ::: xn;1 +1) r;(x1  x2  ::: xn;1) := r(x1  x2 ::: xn;1  ;1) Ha r+ az r^+, r; pedig az r^; polinommal reprezentlt, akkor r-et reprezentlja az

r^(x1  ::: xn) := 1 ;2 xn r^;(x1  ::: xn;1) + 1 +2 xn r^+(x1 ::: xn;1 ) polinom. 4.13 Ttel (Parseval azonossg) hf jgi = 2n PJ n] f^(J )^g(J ) Bizonyts. f -et s g-t rjuk fel spektrlis alakban A skalrszorzat linearitsa s a monomok ortogonalitsa miatt elg az lltst arra az esetre beltni, ha f s g monomok. Erre pedig az llts kvetkezik az 43 "lltsb l 2 A Parseval azonossgot az f = g specilis esetre alkalmazva kapjuk, hogy 4.14 llts X J n] (f^(J ))2 = 1 20 4.2 Ers s gyenge eljelreprezentci 4.15 Denci Egy r pszeudo-Boole fggvnyrl azt mondjuk, hogy az f Boole-fggvnyt er sen el jelreprezentlja, ha 8x 2 V n : sgn r(x) = f (x). (Ezt rviden sgn r = f -nek rjuk.) 4.16 Denci Egy r pszeudo-Boole fggvnyrl azt mondjuk, hogy az f Boole-fggvnyt gyengn el jelreprezentlja, ha r nem azonosan 0, s azon x 2 V n-ekre, amelyekre r(x) 6= 0, sgn r(x) = f (x). Tekinthetj k gy, hogy az r nem foglal llst azokr l az x-ekrl, amelyekre

r(x) = 0. Az ers s gyenge eljelreprezentci (szemben a spektrlis reprezentci val) termszetesen nem egyrtelm, egy Boole-f ggvnyt sok pszeudoBoole f ggvny reprezentlhat. Mi bizonyos rtelemben egyszereket keres nk majd A spektrlis felrs sugall kt termszetes bonyolultsgi mrtket: a fokszmot s a srsget. 4.17 Denci f er s foka: degs(f ) := minfdeg(r) : r ersen eljelreprezentlja f -et g 4.18 Denci f er s srsge: dnss(f ) := minfdns(r) : r ersen el- jelreprezentlja f -et g 4.19 Denci f ersen eljelreprezentlhat S spektrltart val, ha ltezik r, amely ersen eljelreprezentlja, s S (r)  S A gyenge fok (degw (f )) s a gyenge srsg (dnsw (f )), s a gyengn eljelreprezentlhat sg denci ja a fentiekkel teljesen anal g. Plda. Denci szerint minden nemtrivilis THR-f ggvnynek 1 az ers foka, s minden nemtrivilis paritsf ggvnynek 1 az ers srsge. Valamivel sszetettebb plda az EXACT k f ggvny, amelynek ers foka   2 P

legfeljebb 2, mint azt az 12 ; i2n] xi ; k eljelreprezentl polinom mutatja. Konvexitsi megfontolsokb l knnyen levezethet, hogy ha k 6= 0 n, akkor EXACTk ers foka nagyobb 1-nl. Trivilis kapcsolatok denci ink kztt: 4.20 llts degw (f )  degs(f )  deg(f ) 2 4.21;llts degs(f )  d pontosan akkor, ha f ersen eljelreprezentl n] hat d 2 spektrltart val. 21 4.3 Motivci: a perceptronok A szmtsi modell leggyakrabban segdeszkz bonyolulsgelmleti krdsek vizsglatra, s nem azzal az ignnyel alkotjk, hogy mszaki kivitelezsre ker ljn. Van azonban egy modell, amely nagyban hasonlt bizonyos gyakorlatban is hasznlt szmtsi eszkzkre Ez a modell a perceptron 4.22 Denci A perceptron 2 mlysg szintezett hl zat, amelynek els szintje AND-kapukb l ll, msodik szintjn pedig egy THR-kapu van. A perceptront a 40-es vek ta vizsgljk, mint az egyszer neuronhl zatok, specilisan a lt idegek leegyszerstett modelljt MCP]. A perceptronok

irodalmnak mig legfontosabb forrsmve Minsky s Papert 1968-ban megjelent monogrja MP]. Ebben jelennek meg elsknt a eljelreprezentl polinomok, s ez a polinomok els egzakt alkalmazsa bonyolultsgelmleti krdsek megvlaszolsra Trtneti rdekessg, hogy a szerzk mv ket a perceptronok elleni vitairatnak szntk Cla]. A hatvanas vek mestersges intelligencia-kutatsnak egyik npszer irnyzata a perceptront az agy modelllsra alkalmas univerzlis szmtsi eszkznek tekintette, s rvid tv clknt tzte ki val s gondolkodsi feladatokat megold perceptronok ptst. Minsky s Papert egy msik irnyzatot kpviseltek, amely a gondolkods nemfolytonos, szimb lummanipulci s oldalt hangslyozta, s hasonl an rvid tv clja volt gondolkod digitlis szmt gpek ptse. Minsky s Papert bonyolultsgi als becslseiket bizonytknak tekintettk arra, hogy az ellentbor remnyei nem megalapozottak. Termszetesen ma mr senki sem akar gondolkod perceptront pteni, de

Minsky s Papert loz ai vgkvetkeztetse is idejt mlta, hiszen a mestersges intelligencia-kutatsban ma mr az ltaluk preferlt szimb lummanipulci s megkzeltsnl nagyobb a szerepe van a neuronhl zatok elvn alapul anal g, nemtrivilis k dols modelleknek. A Perceptronok meggyzte a mestersges intelligencia-kutat kat a perceptronok gyenge szmtsi kpessgrl, s ez vekkel vetette vissza a mestersges neuronhl zatok kutatst, pedig azok rtatlanok voltak a perceptron legnagyobb hibjban, hogy kicsi a mlysge. Ha a Boole-f ggvnyek denilsakor Igaz s Hamis igazsgrtkeket az ltalunk hasznlt (+1 ;1) helyett a (1 0) szmokkal reprezentljuk, akkor az AND a szorzsnak felel meg. Knnyen lthatjuk, hogy ekkor a perceptron egy polinom eljelt szmtja, ahol az egyes monomok az els szint kapuinak felelnek meg. A perceptron mrete ppen eggyel nagyobb a polinom srsgnl, a perceptron rendje  azaz els szintjnek max-befoka  ppen a polinom fokszma. A

perceptron THR-kapujnak slya pedig a polinom egy tthat inak abszoltrtk-sszege. #gy a perceptron bonyolultsgelmleti 22 vizsglata kzvetlen l visszavezethet a megfelel polinomok algebrai vizsglatra. Sajnlatos m don a (1 0)-reprezentci ra nem igazn alkalmazhat a Fourier-technika. Ezrt az eljelreprezentlssal kapcsolatos ltalunk ismertetett eredmnyek a (+1 ;1)-reprezentci esetre vonatkoznak Lthat , hogy ez az algebrailag kezelhetbb eset annak a mesterkltebb Boole-hl zatosztlynak felel meg, amelynek az els szintjn PAR-kapuk vannak, a msodikon pedig egy THR-kapu. Vegy k szre viszont, hogy az egyik reprezentci r l a msikra val ttrs a bementi vektor egy a%n transzformci jnak felel meg, ezrt nem rinti a reprezentl polinom fokszmt. E szerint egy f ggvny ers foka egyenl a f ggvnyt szmol optimlis rend perceptron rendjvel. A (+1 ;1)-reprezentci ra val ttrs azonban teljesen megvltoztathatja mind a polinom srsgt, mind az egy tthat k

abszoltrtksszegt, s gy hasonl llts nem igaz a perceptron mretre vagy slyra 4.4 Bruck lemmja A pszeudo-Boole f ggvnyek tern denilunk egy normt. Ez nem a mr denilt skalrszorzat ltal induklt norma lesz, hanem egy msik, amely k lnsen alkalmas az eljelreprezentci vizsglatra. Ksbb tovbbi normkat is vizsglunk majd 4.23 Denci Az r 2 R V n fggvny standard l1 -normja: X krk := jr(x)j x2V n Ez lesz a messze leggyakrabban hasznlt normnk, gy ezt egyszeren normnak fogjuk nevezni. A most kvetkez lemma szinte azonnali kvetkezmnye a Parseval azonossgnak (4.13 "llts), de az eljelreprezentci val kapcsolatos sszes eredmny nknek ez fog kiindul pontjul szolglni. 4.24 Lemma (Bruck lemmja) r 2 R V n gyengn eljelreprezentlja n f 2 V V -t akkor s csakis akkor, ha krk = 2n X J n] f^(J )^r(J ): r ersen eljelreprezentlja f -et akkor s csakis akkor, ha krk = 2n s 8x 2 V n : r(x) 6= 0. X J n] 23 f^(J )^r(J )

Bizonyts. Vilgos, hogy ha r gyengn eljelreprezentlja f -et, akkor 8v 2 V n : f (x)r(x)  0: Ez ekvivalens azzal, hogy krk = hrjf i : Alkalmazva a 4.13 Parseval azonossgot ppen a bizonytand lltst kapjuk Az ers eljelreprezntci ra vonatkoz llts ezek utn trivilis. 2 A kvetkez, szintn sokat hasznlt llts j l demonstrlja a Lemma alkalmazhat sgt. Tartalma az, hogy a monomf ggvnyek nem csak linerisan f ggetlenek, de nem llhatnak el ms monomf ggvnyek lineris kombinci jnak signumaknt sem. 4.25 llts Ha r gyengn eljelreprezentlja a K paritsfggvnyt, ak- kor K 2 S (r). Specilisan, degw (PAR) = n Bizonyts. Tegy k fel, hogy r gyengn eljelreprezentlja K -t, s spektrltart ja nem tartalmazza K -t Bruck lemmja szerint krk = 2n X J n] r^(J )cK (J ) = 2nr^(K ) = 0: Ez ellentmond annak, hogy r nem azonosan 0. 2 Egy tovbbi rdekes alkalmazs az albbi: 4.26 Ttel (Rekonstrulhatsgi ttel) Legyen f Boole-fggvny, s r az f ers

eljelreprezentnsa. Legyen tovbb S = S (r) Ekkor f jS  f spektrlis projekci ja S -re , egyrtelm en meghatrozza f -et. Bizonyts. Tegy k fel, hogy ltezik egy g Boole-f ggvny is, amelyre gjS = = f jS . Ekkor g s r is kielgtik az krk = 2n X J n] r^(J )^g(J ) egyenlsget, ezrt r g-t is ersen eljelreprezentlja. Teht g = sgn r = f 2 24 4.5 Alkalmazs: PT1 ( LT2 Most a Fourier-transzformci s technika egyik legels bonyolultsgelmleti alkalmazsval ismerked nk meg. Bruck Bru] denilta elsknt az gynevezett Polinom-k szb (Polynomial Threshold) f ggvnyeket 4.27 Denci PT1 azon Boole-fggvny-sorozatok bonyolultsgi osztlya, amelyeknek ers s r sge a bemenetek szmnak polinomja 1 A perceptronok nyelvn PT1 azon f ggvny-sorozatok osztlya, amelyek szmthat ak olyan 2 mlysg, polinom mret szintezett Boole-hl zattal, amelynek az els szintjn PAR-kapuk, a msodik szintjn egy THR-kapu van. PT1 nagyon b f ggvnycsald, szinte minden ltalunk

eddig denilt Boole-f ggvny-sorozat benne van. Nyilvnval an benne van minden monomf ggvny, minden k szbf ggvny, s minden konstans ers fok Boolef ggvny, mint pldul EXACTk Bruck vette szre elsknt, hogy a PT1 f ggvnyek szmthat ak 2 mlysg, polinom mret THR-hl zatokkal. 4.28 Denci LT2 := (THR-hl zat,poly mret,2 mlysg) Az LT2 osztly nagyon fontos tulajdonsga: 4.29 llts SY MM  LT2 , azaz minden szimmetrikus Boole-fggvny szm that LT2 hl zattal. Bizonyts. Az els szinten a sgn (fk ) f ggvnyeket szmtjuk, amelyek azt llaptjk meg, hogy a bemenet egyeseinek szma legalbb k-e: X fk (x) := xi 2+ 1 ; k ; 12 (k 2 f0 ::: n + 1g) i2n] Vegy k szre, hogy sgn fk (x) ; sgn fk+1(x) 2 egyenl 1-gyel, ha x egyeseinek szma k, minden ms esetben pedig 0. A szimmetrikus Boole-f ggvny rtke csak a bemenet 1-eseinek szmt l f gg. Legyen s(k) az a f ggvny, amely a szmtand Boole-f ggvny rtkt adja Az egyes index az elnevezsben arra utal, hogy Bruck

denilta a P T1 kapukat hasznl k-mlysg, polinom mret hlzatok osztlyt, P Tk -t is. 1 25 a k darab 1-bl ll bemeneten. Ekkor a Boole-f ggvny ppen egyenl a kvetkez kifejezssel: n X k=0 s(k) sgn fk (x) ;2sgn fk+1(x) 2 4.30 Ttel (Bruck) PT1  LT2 Bizonyts. A ttel bizonytsa azon a meggyelsen alapul, hogy az elbbi konstrukci ban nem hasznltuk ki az LT2 teljes erejt. Ugyanis a msodik szinten csak sszegezt nk, de az eredmnynek nem kellett a signumt venn nk. Az elz bizonytsban bevezetett jellssel PAR(x) = 1 + 2 X k2n] (;1)k sgn fk (x): A 8. fejezetben rszleges bizonytst adunk arra a kevss meglep tnyre, hogy ez a konstrukci lnyegben optimlis LT2 hl zatot ad PAR-ra a kapuk szmt tekintve. Mint emltett k, ez a hl zat a msodik szinten mr csak sszegez. Ez alapjn a polinom-k szbf ggvny szmtsa egyszeren gy trtnhet, hogy minden monomjra k ln felpt nk egy az elbb bemutatott PARhl zatot, a msodik szint sszegeit

beszorozzuk a monom egy tthat jval, s az sszes msodik szint kaput sszevonjuk egyetlen sszegg. Az eredmny l kapott hl zat mrete a polinom-k szbf ggvny monomjai szmnak legfeljebb (n + 1)-szerese. 2 Bruck a Fourier-transzformci s technikk tletes alkalmazsval bebizonytotta, hogy a PT1  LT2 tartalmazs val di. Megmutatta, hogy az ltala teljes kvadratikus f ggvnynek (CQ) nevezett szimmetrikus Boole-f ggvny nem eleme PT1-nek. Az 429 "llts ezek utn adja a tartalmazs val disgt Ezt az eredmnyt gy interpretlhatjuk, hogy a poly mret, 2 mlysg hl zatok, amelyeknek mindkt szintje THR-kapukb l ll, hatrozottan ersebb szmtsi kpessg, mint azok a poly mret, 2 mlysg hl zatok, amelyeknek els szintjn csak PAR-kapuk vannak, a msodik szintjn pedig egy THR-kapu. 4.31 Ttel (Bruck) PT1 ( PL2 26 A bizonytshoz visszatr nk az elz fejezetben folytatott vizsglatainkhoz. Az albbiakban a pszeudo-Boole f ggvnyeknek ms normit is fogjuk

hasznlni, mint az eddig megismert k k standard l1-normt. 4.32 Denci A spektrlis l1-norma vagy ^l1-norma: jjrjj1 := max jr^(J )j J n] A spektrlis l1 -norma vagy ^l1 -norma: X jjrjj1 := jr^(J )j J n] Elsknt egy hasznos lemmt bizonytunk a pszeudo-Boole f ggvnyek normir l. Ez az llts egybknt az gynevezett Haussdor-Young egyenltlensg specilis esete 4.33 Lemma krk  2njjrjj1 Bizonyts. Legyen J 2 n] rgztett halmaz krk = kJ rk = = X x X x:(J r)(x)>0 (J r)(x) ; 2 (J r)(x) ; X x:(J r)(x)<0 X x:(J r)(x)<0 (J r)(x)  X x (J r)(x) = (J r)(x) = 2nr^(J ) 2 A lemma segtsgvel als becslst adunk egy Boole-f ggvny ers srsgre. 4.34 Ttel 8f 2 V V n : dnss(f )  1=jjf jj1 Bizonyts. Ha r ersen eljelreprezentlja f -et, akkor X^ jjf jj1jjrjj1  f (J )^r(J ) = 21n krk  jjrjj1  jSjjr(jrj1)j J n] Itt az els egyenltlensg trivilis, a msodik ppen Bruck lemmja, a harmadik az 4.33 Lemma, s az utols ismt trivilis a

spektrltart denci ja alapjn 2 Ez a ttel motivlja az albbi denci t: 27 4.35 Denci PL1 jelli azon Boole-fggvnyek (fggvnysorozatok) csaldjt, amelyekre 1=jjf jj1 fellrl becslhet n polinomjval. A 4.14 "lltsb l tudjuk, hogy a spektrlis egy tthat k ngyzetsszege 1 PL1 teht azokb l a Boole-f ggvnyekbl ll, amelyeknek spektrlis egy tthat i nem egyenletesen kicsik, hanem vannak kzt k kiugr an magasak. 4.36 Kvetkezmny PT1  PL1 2 Megjegyzs. A 4.34 Ttel als becsls az ers srsgre a spektrlis norma f ggvnyben. Bruck s Smolensky a vletlen m dszer felhasznlsval ellenttes irny becslst adott Ezt az eredmnyt csak kimondjuk 4.37 Ttel (Bruck-Smolensky) 8f 2 V V n : dnss(f )  2n(jjf jj1)2 A nem PL1-beli Boole-f ggvnyek egy rdekes osztlya a grbe fggvnyek, amelyekre 8J  n] : jf^(J )j = 2n=2 4.38 Denci CQ(x1  x2 ::: xn) := Li<j (xi ^ xj ) Nyilvnval , hogy CQ szimmetrikus f ggvny, teht a 4.29 "llts szerint benne

van LT2 -ben. Ahhoz, hogy belssuk, hogy CQ 62 PT1, elg beltni,hogy CQ grbe f ggvny: 4.39 Ttel (Bruck) Ha n pros, akkor 8J  n] : jC Qn(J )j = 2n=2  azaz CQn grbe fggvny. A teljesen elemi, de szmolsignyes bizonytst nem kzlj k, megtallhat Bru]-ban. Ezzel a 4.31 Ttelt belttuk, PT1 ( PL2 2 28 5. El jelreprezentci s approximci Smolensky eredmnynek algebrai rsze minden vges testre mkdtt. Anal g eredmny val sok felett is igaz, Aspnes et al ABFR] a Fouriertranszformci elemi tulajdonsgait felhasznlva bizonytja Val sok felett viszont (a lineris egyeltlensgrendszerek bizonyos tulajdonsgainak ksznheten) hasonl erdmnyek nem csak a paritsf ggvnyre igazolhat k. Errl sz l Aspnes et al elegns Alternatvattele A hl zatb l polinomm alakts is hasonl Smolensky konstrukci jhoz, br az a konstrukci nem alkalmazhat kzvetlen l, hiszen a 3.12 Ttel ersen kihasznlta az alaptest vgessgt. Ezt a problmt Valiant s Vazirani egy korbbi

eredmnyre ptve hidaljk t. Csupn megemltj k, hogy ez a konstrukci bizonyos rtelemben  a felhasznlt vletlen bitek szmt tekintve  jobb eredmnyt ad Smolensky vges test feletti konstrukci jnl. Ennek a tnynek a felhasznlsval tbbeknek (AH],KVVY],Tar2]) siker lt az eredetinl j val egyszerbb bizonytst adni Toda hres ttelre To] 5.1 Az Alternatvattel s kvetkezmnyei A lineris egyenltlensgrendszerek elmletnek legalapvetbb eredmnye a Farkas-lemma. A Farkas-lemmnak sok ekvivalens verzi ja ltezik, mi az albbit fogjuk felhasznlni: 5.1 Lemma Legyen U az R m vektortr tetszleges altere Ekkor a kvet- kez kt ll ts kzl pontosan egy teljesl: 1. Ltezik q 2 U , amelyre q 6= 0 q  0 2. Ltezik p 2 U ?, amelyre p > 0 Br ez az ltalunk hasznlt alakb l nem lthat azonnal, Farkaslemmjnak geometriai tartalma: Rgzts nk le egy zrt konvex polidert. Ekkor egy pont akkor s csak akkor nem eleme a polidernek, ha ltezik zrt fltr, amely

tartalmazza a polidert, de nem tartalmazza a pontot. A bizonyts megtallhat brmely lineris programozssal foglalkoz monogrban, pldul Chv]-ban. Ltni fogjuk, hogy Farkas Lemmjnak szinte kzvetlen kvetkezmnye egy olyan llts, amelynek segtsgvel sok Boole-f ggvny (pldul minden szimmetrikus Boole-f ggvny) gyenge s ers fokt meghatrozhatjuk. 5.2 llts Legyen f 2 V V n , s U legyen a R V n vektortr tetszleges altere. A kvetkez kt ll ts kzl pontosan egy teljesl: 29 f gyengn eljelreprezentlhat U -beli pszeudo-Boole fggvnnyel. f ersen eljelreprezentlhat U ?-beli pszeudo-Boole fggvnnyel. Bizonyts. Vegy k szre, hogy az lltst elg arra az esetre bizonytani, amikor az f az azonosan 1 Boole-f ggvny. (Ezt a f ggvnyt a tovbbiakban 1-gyel jellj k.) Ugyanis vlaszthatunk egy  ortogonlis transzformci t psz-en, amely az f -et 1-be viszi, s erre ((U ))? = (U ?). Alkalmazva Farkas Lemmjt ezutn pontosan a bizonytand lltst

kapjuk. 2 Fontos specilis eset, amikor az U nhny monom ltal generlt altr. Ennek tovbbi specilis esete, amikor U a legfeljebb d fok monomok ltal generlt altr. Kimondjuk a ttel ezen specilis eseteknek megfelel vltozatait 5.3 Ttel Legyen f 2 V V n , s S  2n] A kvetkez kt ll ts kzl pontosan egy teljesl: 1. f gyengn eljelreprezentlhat S spektrltart val 2. f ersen eljelreprezentlhat 2n] n S spektrltart val 2 5.4 Ttel Legyen f 2 V V n , d 2 f0 ::: ng A kvetkez kt ll ts kzl pontosan egy teljesl: 1. degw (f )  d 2. degs(f PAR)  n ; d Msknt fogalmazva: Minden f 2 V V n -re degw (f ) + degs(f PAR) = n: Bizonyts. Alkalmazzuk az 53 Ttelt az S = ; n  esetre. Az llts d bizonytshoz ezutn csak arra a meggyelsre van sz ksg, hogy f pontosan akkor ersen eljelreprezentlhat; fS : S  n] jS j > dg spektrltart val, ha f PAR ersen reprezentlhat nn;d spektrltart val, hiszen xJ PAR = xn]nJ : 2 Most az 5.4 Ttel

alkalmazsaknt meghatrozzuk egy tetszleges szimmetrikus Boole-f ggvny gyenge s ers fokt Ehhez elbb egy denci 30 5.5 Denci Legyen f szimmetrikus Boole-fggvny f eljelvltsainak szmt gy de niljuk, mint az a0 := f (;1 ;1 ;1 ::: ;1) a1 := f (+1 ;1 ;1 ::: ;1) a2 := f (+1 +1 ;1 ::: ;1) . an := f (+1 +1 +1 ::: +1) sorozat eljelvltsainak szmt. 5.6 Kvetkezmny Legyen f szimmetrikus Boole-fggvny f gyenge s ers foka egyarnt egyenl f eljelvltsainak szmval. Bizonyts. Legyen az f eljelvltsainak szma k Ekkor knnyen konst- rulhatunk olyan g egyvltoz s polinomot, amelynek a signuma az m helyen azonos az elz denci ban megadott fag sorozat m-dik tagjval, s fokszma k. A 1 0 X g @ xi 2+ 1 A i2n] legfeljebb k fok polinom ersen eljelreprezentlja f -et. Ezzel belttuk, hogy degs(f )  k. A fordtott irny egyenltlensg bizonytshoz tekints k az f PAR Boole-f ggvnyt f PAR eljelvltsainak szma lthat an ppen n ; k. A

fentiek szerint teht degs(f PAR)  n ; k (n ; k) + k  degs(f PAR) + degs(f )  degs(f PAR) + degw (f ) = n: Itt az els egyenltlensg elbbi meggondolsaink eredmnye, a msodik a trivilis 4.20, a harmadik pedig ppen az 54 Ttel Minden tt egyenlsg ll, amibl a bizonytand llts azonnal kvetkezik. 2 Az lltsb l ltszik, hogy egy tipikus szimmetrikus Boole-f ggvny gyenge foka n=2. Feltehetj k a krdst ltalnos Boole-f ggvnyekre is Aspnes et al az albbi meglep sejtst fogalmazza meg 31 5.7 Sejts (Aspnes et al) A 2m-vltoz s f Boole-fggvnyek (1;o(1)) rszre degw (f ) = m. A 2m + 1-vltoz s f Boole-fggvnyek (1=2 ; o(1)) rszre degw (f ) = m, s msik (1=2 ; o(1)) rszre degw (f ) = m + 1. Ebben az irnyban Gotsman Got] is rt el eredmnyeket, de a legersebb becsls Razborov s Rudich RR] munkja. &rdekessgknt megjegyezz k, hogy Razborovk ezen eredmny alapjn bizonyos negatv kvetkeztetseket vontak le Aspnes et al. m dszereinek lesthetsgrl

5.8 Ttel (Razborov-Rudich) Az n-vltoz s f Boole-fggvnyek (1 ; ; o(1)) rszre degw (f )  n=20: Ezt az lltst nem bizonytjuk. 5.2 Approximci a valsok felett 5.9 Denci Az f Boole-fggvnyt az r pszeudo-Boole fggvny " hibval approximlja, ha legfeljebb 2n" darab x 2 V n cs cs kivtelvel r(x) = = f (x). Az f Boole-fggvnyt az r pszeudo-Boole fggvny " hibval el jelapproximlja, ha legfeljebb 2n" darab x 2 V n cs cs kivtelvel sgn r(x) = f (x). Felhvjuk a gyelmet a 3.8 Denci val val anal gira Ksbb, az 5.13 Denci ban, csakgy mint a Z3 feletti approximci denci jt, ezt is kiterjesztj k tetszleges bemeneti val sznsgeloszls esetre. Most kvetkez ttel nkkel kapcsolatba hozzuk egy f ggvny eljelapproximlhat sgt a gyenge fokval. 5.10 Ttel (Aspnes et al) Tegyk fel, hogy egy f Boole-fggvnyt egy r polinom gy eljelapproximl, hogy a hibz pontok halmaza S  V n. Legyen k 2 n] a legkisebb olyan szm, amelyre jS j <

Ekkor n k : deg(r)  degw (f ) ; 2k 32 Bizonyts. A bizonyts azon alapul, hogy az S halmazhoz keres nk egy olyan polinomot, amelynek kicsi a fokszma, sehol sem negatv, nem azonosan 0, de S minden elemn 0. Ezzel megszorozva az eljelapproximl polinomot az eredmny gyengn eljelreprezentlja f -et. Nem meglep m don ezt a sehol sem negatv polinomot egy olyan polinom ngyzeteknt fogjuk keresni, amelynek kicsi a fokszma, nem azonosan 0, de S minden elemn 0. Ennek ltezst szavatolja az albbi lemma 5.11 Lemma Ha S  V n, s jS j < ; n , akkor ltezik olyan p(x) nem k azonosan 0, k-adfok polinom, amely S -en azonosan 0. A Lemma bizonytsa. Egy n-vltoz s k-adfok polinomnak ; n  egy tthat egyes pontjain felvett rtkei ezeknek lineris kombinci i. (Ezeket a lineris kombinci kat egzakt m don meg is adtuk a 4.10 "lltsban) #gy az, hogy a polinom rtke egy adott pontban 0, egy homogn lineris egyenlsggel rhat fel, melynek vltoz i a polinom

k-nl nem nagyobb fok monomjainak egy tthat i. Az, hogy a p az egsz S; -en eltnik, e szerint azzal ekvivalens, hogy p egy tthat i egy jS j sorb l s n;k oszlopb l  n ll homogn lineris egyenletrendszert kielgtenek. Az jS j < k felttel miatt ennek ltezik nemtrivilis megoldsa, ami ppen a keresett polinomnak felel meg. 2 ja van, s V n k A Ttel bizonytsa. Szorozzuk meg r-et az elz lemma ltal adott p polinom ngyzetvel. Az eredmny fokszma deg(r) + 2k, s gyengn eljelreprezentlja f -et A gyenge fok denci ja szerint deg(r) + 2k  degw (f ) 2 Most alkalmazzuk a PAR f ggvnyre a fentieket, megkapva ezzel a 3.9 Ttel megfeleljt a val s eljelapproximci esetre. 5.12 Kvetkezmny Egy pn fok pszeudo-Boole fggvny a PAR Boole-fggvnyt csak (1) hibval kpes eljelapproximlni. Bizonyts. Tegy k fel, hogy az r pszeudo-Boole f ggvny fokszma pn, s az S  V n halmaz pontjait l eltekintve eljelreprezentlja PAR-t. A 425 Kvetkezmny szerint degw (PAR) = n.

Alkalmazzuk az 510 Ttelt: p n  n ; 2k 33 ;  ahol k a legkisebb olyan szm, amelyre jS j < nk . p n k  2 ; 2n A Cherno-korlt (3.10 "llts) alkalmazsval ppen a bizonytand lltst kapjuk 2 5.3 AND approximlsa Most bizonytjuk azt a ttelt, amely Smolensky 3.12 Ttelnek kzvetlen megfelelje a val s szmtest feletti approximci -fogalomra. 1990-91-ben egymst l tbb-kevsb f ggetlen l tbb kutat csoport is BGS2]ABFR] Tar2]AH] megalkotta a ttelt lnyegben azonos formban. Emlkeztet nk r, hogy a 3.12 Ttel szerint az AND tetszleges bemeneti eloszls mellett kis hibval approximlhat a Z3 feletti kis fokszm polinommal. Elszr megadjuk a 3.11 Denci megfeleljt a val s esetre 5.13 Denci Legyen  val sz n sgeloszls a V n halmazon f legyen Boole-fggvny, r pszeudo-Boole fggvny. Azt mondjuk, hogy r az f -et " hibval approximlja a  bemeneti eloszls mellett, ha Pr (f (x) = r(x))  " Azt mondjuk, hogy r az f -et " hibval el

jelapproximlja a  bemeneti eloszls mellett, ha Pr (f (x) = sgn r(x))  " Beigel-Reingold-Spielman, Aspnes-Beigel-Furst-Rudich, Tarui, AllenderHertrampf eredmnye: 5.14 Ttel Legyen l pozit v egsz, s  tetszleges val sz n sgeloszls V n-en. Ekkor az n-vltoz s AND-fggvnyhez ltezik a racionlisok feletti l log n-fok polinom, amely (2=3)l hibval approximlja a  bemeneti eloszls mellett. Megjegyzs. Hangslyozzuk, hogy nem eljelaprroximci r l, hanem approximci r l van sz Bizonyts. A bizonyts hasonlt a 312 Ttel bizonytshoz, de sz ksg van egy j tletre. Ez Valiant s Vazirani egy korbbi lemmja VV] Az alfejezet htralv rszben k := dlog ne + 1. Legyen J  n], J 6=  Deniljuk a fZi : i 2 k]g vletlen halmazsorozatot az albbi m don: Z1 := n], s Zi+1-et gy kapjuk Zi-bl, hogy Zi minden elemt egymst l f ggetlen l 12 val sznsggel kihagyjuk. 34 5.15 Lemma (Valiant-Vazirani) Pr(9i 2 k] : jZi J j = 1)  1=3 A lemmnak megadjuk egy Lukcs

Andrst l szrmaz szemlletes tfogalmazst: Egy radioaktv atom felezsi ideje pontosan egy nap. Ellltunk belle egy tetszleges d zist. Ezek utn minden nap pontban dlben megvizsgljuk az elbomlatlan anyag mennyisgt Ekkor Valiant s Vazirani lemmja szerint legalbb 1=3 val sznsggel lesz olyan nap, amikor a dli vizsglat pontosan egy atomot tall. A Lemma bizonytsa. A tmrebb trgyals kedvrt bevezetj k az albbi jellst: pi := jZi J j Az albbi hrom eset kz l pontosan egy ll fenn. I. eset p1 = 1 II. eset pi > 1 minden i 2 k]-ra Ennek val sznsge legfeljebb n2;k   1=2. III. eset Valamilyen i 2 k ; 1]-re pi > 1, de pi+1  1 Tetszleges j -re az albbi feltteles val sznsgek: Pr(pj+1 = 0jpj = m) = 2;m Pr(pj+1 = 1jpj = m) = m2;m Ezrt m  2 esetn ;m Pr(pj+1 = 0 j (pj = m) ^ (pj+1 = 0 1)) = m2;2m + 2;m = m 1+ 1  31 E szerint arra az i-re, amelyre pi > 1, s pi+1  1, legalbb 2=3 val sznsggel pi+1 = 1. A I. s III eset egy tt legalbb 1=2

val sznsg, teht legalbb 1=3 annak a val sznsge, hogy valamely i 2 k]-ra pi = 1. 2 A lemma segtsgvel k-adfok vletlen polinomot alkotunk, amely legalbb 1=3 val sznsggel ;1, ha a bemenet nem azonosan 1, s mindig 1, ha a bemenet azonosan 1. Legyen fZi : i 2 k]g a lemmban szerepl vletlen halmazsorozat. pi-vel most polinomot jell nk pi(x) := X xj + 1 i 2 k] 2 ;xj 2Zi pi(x) ppen az x-ben Zi-beli pozci ban lev (;1)-ek szmval egyenl. 35 Deniljuk a p vletlen, k-adfok polinomot: p := Yk i=0 (1 ; pi) Ha x azonosan 1, akkor minden pi(x) = 0, teht p(x) = 1. Ellenkez esetben a Lemma szerint legalbb 1=3 val sznsggel valamelyik pi(x) egyenl 1-gyel, s a szorzat nulla lesz. 2p ; 1 teht legalbb 1=3 val sznsggel egyenl AND(x)-szel. Innen a bizonyts technikja azonos a 3.12 Ttel bizonytsval elszr ismtlssel cskkentj k a hibt, majd ketts leszmllst alkalmazunk. A hiba cskkentshez vlasszuk a p(1)  p(2)  ::: p(l) polinomokat

gy, hogy a denil fZig vletlen halmazsorozatok egymst l f ggetlenek legyenek. Tekints k a 0 1 (i) Y 2 @ p + 1A ; 1 i2l] 2 polinomot. Ez a val sznsgi vltoz -polinom minden x bemenetre legfeljebb (2=3)l val sznsggel hibzik Van teht egy polinomcsaldunk, amely csupa l log n fok polinomb l ll, s minden x-re legalbb az (1 ; (2=3)l)edrsz k j l reprezentlja AND-et. A ttel bizonytshoz mr csak egy ketts leszmllst kell alkalmazni. Ebbl kvetkezik, hogy van olyan eleme a polinomcsaldnak, amely a  bemeneti eloszls mellett (1 ; (2=3)l) val sznsggel egyenl AND-del. Ezzel az lltst bizonytottuk 5.4 Boole-hlzatbl polinom Ez a fejezet szintn hasonltani fog a megfelel 3.3 Fejezetre Ott a vges test hasznlata lehetv tette a MOD3-kapuk hasznlatr l sz l 3.1 ltalnostst a klasszikus 213 Ttelnek Mint ltni fogjuk, itt a val sok hasznlata egy ms irny ltalnostst tesz lehetv. 5.16 Lemma Legyen l 2 N Ha egy fAND OR NOT g-hl zat mrete N

s mlysge k, akkor a hl zat approximlhat N=2l hibval egy val sok feletti (2l)k fokszm polinommal. Bizonyts. Els lpsknt a deMorgan-szably alkalmazsval az OR- kapukat lecserlj k AND s NOT kapukra. Ez a hl zat mrett legfeljebb meghromszorozza. 36 A hl zatot a bemenetektl a kimenetek fel haladva topologikus sorrendben (2.4 Denci ) kapunknt alaktjuk polinomm Kezdlpsknt az xi bemeneteket az xi polinomokkal reprezentljuk. (i 2 n]) Ha egy kapu sorra ker l, akkor a topologikus sorrend denci ja szerint a bemeneteire mr megadtuk az approximl polinomokat. Legyenek ezek g1(x) g2(x) ::: gm (x). Kt esetet k lnbztet nk meg aszerint, hogy milyen kapur l van sz . I. eset: NOT -kapu A kimenet ekkor 0 hibval reprezentlhat a ;g1 polinommal, amely a bemenet elsfok polinomja II. eset: AND-kapu A V n halmazon vett egyenletes eloszls indukl egy  eloszlst a (g1(x) g2(x) ::: gm (x)) vektorra nzve. Az induklt  eloszlsra alkalmazzuk a 5.14 Ttelt Ez

egy olyan h m-vltoz s polinomot ad, amely 1 ; 1=2l -val sznsggel a gi bemenetek AND f ggvnye lesz.  vlasztsa s az induklt eloszls denci ja miatt a h(g1(x) :::gm (x)) polinom 1=2l hibval approximlja az AND(g1(x) :::gm (x)) f ggvnyt, ha az x-et egyenletes eloszlssal vlasztjuk V n-bl. sszefoglalva: a kapu kimenete minden esetben approximlhat a kapu bemeneteinek legfeljebb (2l)-fok polinomjval, gy, hogy a hl zat azon inputjainak arnya, amelyekre ez a kapu hibs eredmnyt ad, legfeljebb 1=2l . Az i. szinten az elz szintek kapuib l alkotott polinomok legfeljebb (2l)fok polinomjai szerepelnek #gy a fokszm minden szinten az elz szint maximlis fokszmnak (2l)-dik hatvnyval becs lhet. A teljes fokszm teht legfeljebb (2l)k . Minden egyes kapu a bemenetek (nem a sajt bemenetei, hanem a legals szint bemenetei) legfeljebb 1=2l-ed rszn hibzik. #gy a globlis hiba legfeljebb N=2l . 2 5.17 Ttel PAR nem szm that olyan k mlysg , 2o(n = k ) mret 1 2

fAND OR NOT g-Boole-hl zattal, amelynek a legfels szintjn egy THRkapu van. Bizonyts. Vlasszuk l-et ( 21 n1=2k )-nak, s alkalmazzuk az elz lemmt a PAR Boole-f ggvnyt szmt hl zat legfels THR kapujnak sszes bemenetre. Ezek utn rtelemszer m don a hl zat kimenett el jelapproximlhatjuk a polinomok Ekkor a nyert p egy lineris f ggvnyvel. 1=2n =2k polinom fokszma ppen n, s a polinom N=p (2 ) hibval eljelapproximlja PAR-t. A 512 Ttel szerint egy n fok polinom PAR-t (1) hibval kpes csak approximlni. Teht 1 N = (2 37 1 2 n1=2k ) s ezzel a 5.17 Ttel bizonytst befejezt k 2 6. "-kzelts A Boole-f ggvnyek eddig bevezetett algebrai reprezentci i s azoknak megfelel bonyolultsgi mrtkei (az approximlhat sg k lnbz verzi i, gyenge s ers fok) utn most egy olyant trgyalunk, amely taln mg az elbbieknl is termszetesebb. 6.1 Denci Legyen 0  " < 1 Az f Boole-fggvnyt az r pszeudoBoole fggvny "-kzelti, ha

8x 2 V n : jf (x) ; r(x)j  ": 6.2 Denci Az f Boole-fggvny "-kzelt foka, deg"(f ) a legkisebb fok pszeudo-Boole fggvny foka, amely "-kzel ti f -et. Denci nk azonnali kvetkezmnyei: 6.3 llts deg0(f ) = deg(f ) deg"(f )  deg(f ) Felmer l a krds, hogy becs lhet-e alulr l nemtrivilis m don deg(f )nek valamilyen f ggvnyvel deg"(f )? Ezt a krdst vlaszolja meg Nisan s Szegedy dolgozata NS]. 6.4 Ttel (Nisan-Szegedy) Minden x 0  " < 1 mellett deg(f ) = O(deg8" (f )) minden f Boole-fggvnyre, A Ttel szerint teht ha egy f ggvny fokszma nagy, akkor kzelteni sem lehet sokkal kisebb fokszmmal. Nisan s Szegedy bizonytsban a kulcslemma nem ms, mint a ttel bizonytsa egy specilis esetben. Mi a kvetkez alfejezetben NS] nyomn bizonytjuk ezt a specilis esetet. (615 Ttel) A becslshez Nisan s Szegedy ezutn tbb egyenltlensget kel kzbe, melyek Nisan Nis2] illetve Blum-Impagliazzo BI] korbbi eredmnyei.

&rdekes m don br a becsls kt algebrai jelleg mennyisget hoz kapcsolatba, a kzbekelt mennyisgek kztt van kombinatorikai (a blokkszenzitivits), s bonyolultsgelmleti jelleg (a dntsi fa mlysg s CREW PRAM bonyolultsg). Ezeket a mennyisgeket nem deniljuk &ppen a tbblpcss becsls az oka, hogy a meglehetsen nagy 8-as kitev megjelenik a becslsben. Nisan s Szegedy azt sejtik, hogy ez tvol van az optimlist l: 38 6.5 Sejts (Nisan-Szegedy) Minden x 0  " < 1 mellett deg(f ) = O(deg2" (f )) minden f Boole-fggvnyre. Most deniljuk az approximci elmletben alapvet fontossg Csebisev polinomokat. 6.6 Denci Ha jxj  1, akkor Tn (x) := cos(n arc cos x): Ha jxj  1, akkor Tn(x) := ch (n arch x): Tn ppen egyenl egy n-edfok polinommal. Ezt nevezzk az n-dik Csebisev polinomnak A Csebisev-polinomok legfontosabb tulajdonsgait sszefoglaljuk. Bizonytsuk megtallhat brmelyik approximci elmleti monogrban, mint pldul Riv]. 6.7

llts I. tulajdonsg jTn(x)j  1, ha jxj  1 II. tulajdonsg jTn0 (x)j  n2 , ha jxj  1 III. tulajdonsg jTn0 (x)j  n2, ha jxj  1 A Csebisev-polinomok segtsgvel knnyen konstrulhatunk kis fokszm, az OR f ggvnyt kzelt pszeudo-Boole f ggvnyt. 6.8 llts Minden elg nagy n-re 2 p 1 deg"(OR)  p arch " n: 2 Bizonyts. Legyen c pozitv val s, s k := cpn Tekints k a ;  T x p(x) := k ; n;n 1  Tk n;1 39 egyvltoz s polinomot. Elemi becslsekbl levezethet, hogy  n  p k  p Tk n ; 1  ch 2 pn = ch ( 2c): Ez a p polinom teht p az n-ben 1, s 0  x  n ; 1-re p(x) abszolt rtkben legfeljebb 1=ch ( 2c). Ebbl kvetkezik, hogy a 1 0 X 1 ; 2p @n ; xi + 1 A i2n] 2 p pszeudo-Boole f ggvny 2=ch ( 2c) hibval kzelti az OR f ggvnyt. Ha adott az " hiba, akkor a megfelel c ebbl kiszmthat , s ppen az lltsban megkveteltnek ad dik. 2 Ez a plda mutatja, hogy az 6.5 Sejts tovbb nem lesthet, hiszen degOR = n. 6.1 A Szimmetrizcis

Lemma Legyen f szimmetrikus pszeudo-Boole f ggvny. Ekkor f -nek megfeleltethetj k azt az f~ legfeljebb n-edfok egyvltoz s polinomot, amelyre f~(k) = f (;1 ;1 ::: ;1 +1  ::: +1 +1) ahol a +1-ek szma k. Az f~ polinom egyrtelm, hiszen (n + 1) ponton interpoll. 6.9 llts degf = degf~ Bizonyts. Vilgos, hogy a 0 1 X g(x) := f~ @ xi + 1 A i2n] 2 degf~-fok polinom interpollja az f pszeudo-Boole f ggvnyt. Ez a polinom nem felttlen l multilineris. Multilinearizltjt jellj k h-val (36 Denci ) A multilinearizls a fokszmot csak cskkentheti, ami mutatja, hogy degf  degf~. A g maximlis fok monomjai a 0 1 X @ xi + 1 A 2 i2n] 40 kifejezs degf~-edik hatvnyra emelsvel llnak el. A hatvnyozst elvgezve lthat , hogy h maximlis fok monomjai ppen a n vltoz b l kpezett degf~ darab csupa k lnbz tnyezbl ll szorzatok, azonos egy tthat val Ebbl azonnal kvetkezik, hogy degh = degf:~ A spektrlis alak egyrtelmsge miatt f azonos h-val. 2 Most

deniljuk egy f ggvny szimmetrizltjt. A denci Minsky s Papert nevhez fzdik MP]. (k az albb bizonytand Szimmetrizci s Lemmt arra hasznltk, hogy levezessk a degs(PAR) = n egyenlsget, dolgozatunk 4.25 "lltst 6.10 Denci Legyen r 2 R V n r szimmetrizltja X r(x(1)  ::: x(n) ): rsymm(x1  ::: xn) := n1! 2Sn (Sn az n] permutci csoportja.) Ugyanez a formula de nilja egy n-vltoz s polinom szimmetrizltjt. A szimmetrizci egy pszeudo-Boole f ggvnyhez hozzrendeli azt a pszeudo-Boole f ggvnyt, amely az sszes k darab +1-et tartalmaz bemenetre ugyanazt az rtket veszi fel: az eredeti f ggvnynek a k darab +1et tartalmaz bemeneteken vett tlagt. Vilgos, hogy egy pszeudo-Boole f ggvny szimmetrizltja szimmetrikus pszeudo-Boole f ggvny, s egy polinom szimmetrizltja szimmetrikus polinom. Szimmetrikus pszeudo-Boole f ggvny szimmetrizltja nmaga. A szimmetrizci taln legfontosabb tulajdonsga, hogy nem nveli a fokszmot: 6.11 Lemma degrsymm  degr

Bizonyts. Ha r spektrlis alakja a multilineris r^ polinom, akkor r szimmetrizltjnak spektrlis alakja ppen az (^r)symm multilineris polinom Ez ut bbi az r^(x(1)  ::: x(n) ) polinomok tlaga, s ezek mindannyian degr fok polinomok. Ebbl az llts kvetkezik 2 Az f 7! f~ lekpezst eddig csak szimmetrikus pszeudo-Boole f ggvnyekre deniltuk. 6.12 Denci Egy f tetszleges pszeudo-Boole fggvnyre a f~ egyvlsymm kplettel de niljuk toz s polinomot a f^ A 6.9 "llts s a 611 Lemma kvetkezmnye: 6.13 Lemma (Szimmetrizcis Lemma) degf~  degf 2 41 6.2 Becsls az OR f ggvnyre Elszr bizonyts nl l kimondunk egy alapvet approximci elmleti lemmt. 6.14 Lemma (Markov) Legyen p egyvltoz s d fok val s polinom, s a1 a2 ] tetszleges intervallum. Legyen b olyan pozit v val s, hogy minden a1  x  a2 -re ;b  p(x)  b. Ekkor a1  a2] minden x elemre 2d2b : a2 ; a1 Nisan s Szegedy ezt a lemmt felhasznlva als becsls adnak egy specilis Boole-f

ggvny-osztly kzelt fokra. Fontos megjegyezn nk, hogy az OR f ggvny benne van ebben az osztlyban. jp0 (x)j  6.15 Ttel (Nisan-Szegedy) Ha az f Boole-fggvny a csupa ;1 cs csban ;1, s az sszes szomszdos cs csban +1, akkor r 1 ; " n: 2 Bizonyts. Tegy k fel, hogy r a kvnt mrtkben kzelti f -et Alkalmazzuk a Szimmetrizci s Lemmt (613 Lemma) r-re Egy p := r~ egyvltoz s polinomot kapunk, amelynek fokszmt jellj k d-vel. p a kvetkez tulajdonsgokkal rendelkezik: 0. d  degr I. ;1 ; "  p(0)  ;1 + " (hiszen p(0) = r(;1 ;1 ::: ;1)) II. +1 ; "  p(1)  +1 + " III. ;1 ; "  p(k)  +1 + ", ha 2  k  n egsz I.-bl s II-bl a Lagrange-fle kzprtkttel szerint kvetkezik, hogy ltezik olyan 0  x  1, hogy IV. jp0(x)j  (+1;"1);;(0;1+") = 2(1 ; "): q 1;Be" fogjuk ltni, hogy a III. s IV felttelt kielgt polinom legalbb 2 n fok. Ha egy intervallumon egy polinom minden tt kicsi, de a derivltja nem

minden tt kicsi, akkor a Markov-lemma szavatolja, hogy a polinom fokszma nagy. Mi a III felttel szerint nem egy intervallumon, hanem csak egy intervallum egsz pontjain tudjuk a polinomr l, hogy kicsi Most kiterjesztj k a deg"(f )  42 becslst a teljes intervallumra: c := maxfjp0(x)j : 0  x  ng (IV. szerint c  2(1 ; ")) III.-b l a Lagrange-fle kzprtkttel segtsgvel kvetkezik ;1 ; " ; c=2  p(x)  +1 + " + c=2: Most mr alkalmazhatjuk a Markov-lemmt: c  2d (1 +n" + c=2) 2 "trendezve: 2(1 ; ")n = 1 ; " n:  d2  c + cn 2 + 2" 2(1 ; ") + 2 + 2" 2 Ebbl az O. llts alapjn a bizonytand llts mr kvetkezik 2 A 6.8 "lltst gyelembe vve ezzel megkaptuk, hogy 6.16 Kvetkezmny Minden rgz tett 0 < " < 1-re p deg"(OR) = ( n): A 7. Fejezetben mg visszatr nk az OR f ggvny kzelt foknak krdsre Br a 6.15 Ttel csak egy meglehetsen specilis f ggvnyosztlyra ad als becslst,

de Nisan s Szegedy megmutattk, hogy ez alapjn mr minden Boole-f ggvny kzelt fokra adhat becsls. Mint mr emltett k, mi ezt nem bizonytjuk. Most bemutatjuk a 6.15 Ttel egy tovbbfejlesztett vltozatt Pat] 6.17 Ttel (Paturi) Egy f szimmetrikus Boole-fggvnyre ;(f ) := minfj2k ; n + 1j : f~(k) 6= f~(k ; 1) 0  k < ng: Ekkor Specilisan p deg2=3 (f ) = ( n(n ; ;(f ))): deg2=3 (MAJ ) = (n): 43 Itt ;(f ) nem ms, mint annak az n=2-re szimmetrikus, egsz intervallumnak a hossza, amelyen f~ konstans. Paturi ttelnek bizonytsa Markov lemmjhoz (6.14 Lemma) hasonl nemtrivilis approximci elmleti als becslseken alapul. Ezek az eredmnyek szintn polinomok intervallumon val viselkedsrl sz lnak Nisan s Szegedy bizonytsban fontos lps a diszkretizci . (#gy nevezz k a bizonytsnak azt a lpst, amikor a 0 n] intervallumon val viselkedsrl sz l approximci elmleti eredmnybl hasonl eredmnyre kvetkeztet nk a f0 ::: ng vges halmazon.) Nisan s

Szegedy bizonytsban a diszkretizci a Lagrange-fle kzprtkttel alapjn lnyegben nyilvnval volt Paturi bizonytsban a nehzsg abb l ad dik, hogy ez esetben az les eredmny elrshez nem elegend a kzprtkttel hasznlata. Paturi bizonyos trigonometrikus polinomok konstrulsnak segtsgvel hidalja t ezt a nehzsget, amelyekkel beszorozva a szimmetrizltat az eredetileg csak egsz pontokban kicsi polinom a teljes intervallumon kicsiv vlik, mikzben a derivlt egy kit ntetett pontban nem cskken. 7. "-kzelts adott spektrltartval Most azt a krdst fogjuk vizsglni, hogy adott f 2 Vn V n , adott 0  " < 1 s adott S spektrltart mellett ltezik-e olyan r 2 R V , amely S spektrltart val "-kzelti f -et. Eredmny nk egy Aspnes et al ttelhez (53 Ttel) hasonl alternatvattel lesz, amelynek a kvetkez fejezetben bemutatjuk nhny alkalmazst is. 7.1 Alternatvattel az "-kzeltsrl Az, hogy egy r 2 R V n egy f 2 V V n Boole-f

ggvnyt "-kzelt, egy lineris egyenltlensgrendszerrel rhat le. Azt, hogy S (r)  S (specilisan hogy r foka  d), egy homogn lineris egyenletrendszerrel fejezhetj k ki. #rjuk fel ezeket. A felrshoz egyarnt sz ksg nk lesz a standard s a spektrlis alakra. Mint mr lttuk (410 "llts), ha r-et a cscsokkal indexelt, s r^-ot a monomokkal indexelt 2n-dimenzi s vektornak tekintj k, akkor a Fouriertranszformci egy olyan lineris transzformci , melynek tmenetmtrixa egy Sylvester-fle H Hadamard-mtrix: r^ = 21n Hr r = H r^ Ha kiktj k, hogy S (r)  S , akkor az r^ vektor S -en kv li elemei eltnnek. Ekkor r^ helyett tekinthetj k azt az r^jS vektort, amelynek elemei S 44 elemeivel vannak indexelve. Ez esetben az r = H r^ transzformci s kplet termszetesen az r = H jS r^jS alakba megy t, ahol H jS az a mtrix, amely H S elemeivel indexelt oszlopaib l ll. A rvidsg kedvrt r^jS helyett rjunk x-et. Az, hogy ltezik S tart j, f -et "-kzelt r, ezek

utn gy rhat : 9x 2 R S : ;  H j x  f + "1 S ;H jS x  ;f + "1 (Itt 1 az azonosan 1 Boole-f ggvnyt jelli.) Farkas lemmjnak egyik vltozatt (5.1 Lemma) mr alkalmaztuk Aspnes et al Alternatvattelnek (53 Ttel) bizonytsakor Most egy msik vltozatot fogunk hasznlni, s a megfogalmazs m djt is megvltoztatjuk, alkalmazkodva fejezet nk nyelvezethez. 7.1 Ttel Legyen A 2 R n] , b 2 Rn] . De nilunk kt egyenltlensgrendszert Priml: Ax  b (x 2 R n] ) Dul: yA = 0, hyjbi < 0 (y 2 R m] ) A priml s a dul egyenltlensgrendszer kzl pontosan egy oldhat meg. m] ;  Ha -ot vlasztjuk a priml egyenltlensgrendszernek, akkor a dulis egyenltlensgrendszer knnyen lthat an ;  y1H jS + y2(;H jS ) = 0 hy1 jf + "1i + hy2 j ; f + "1i < 0 Itt y1 y2 2 R V n , s ezek sorvektornak tekintendk. "trendezs utn: (y1 ; y2)H jS = 0 hy1 ; y2 jf i + " hy1 + y2 j1i < 0 Ebbl az alakb l lthat , hogy ha y1 y2 megolds, s egy v 2

V n indexre y1(v) > 0 y2(v) > 0, akkor mindkettbl egy kis val s szmot levonva y1 y2 megolds marad, hiszen y1 ; y2 nem vltozik, hy1 + y;2j1i pedig cskken. #gy teht feltehetj k, hogy olyan megoldsunk van -ra, amelyre n 8v 2 V : y1 (v )y2(v ) = 0 Ezutn y := y2 ; y1, s ekkor (y1 + y2)(v) = jy(v)j, amibl hy1 + y2j1i = = kyk kvetkezik. 45 Eddigi talaktsaink eredmnye: ; pontosan akkor oldhat meg, ha ltezik y 2 R V n : yH jS = 0 hyjf i > > "kyk Az yH jS = 0 felttel knnyen rtelmezhet. &ppen azt jelenti, hogy S (y) diszjunkt S -tl. Az hyjf i > "kyk felttel viszont annyira lnyeges lesz ksbbi vizsglataink sorn, hogy erre nnll denci t vezet nk be: 7.2 Denci Legyen 0  " < 1 Egy y 2 R V n "-fedi az f 2 V V n fggvnnyel, ha hyjf i > "kyk. A szoksos m ndon azt mondjuk, hogy f "-fedhet S spektrltartval, ha ltezik r 2 R V , ami "-fedi f -et, s S (r)  S . A fedsnek ez a denci ja nem igazn

szemlletes, nem ltszik belle az sem, hogy itt valamilyen rtelemben kzeltsrl van sz . Ezrt megadunk egy nyilvnval an ekvivalens, de tlthat bb denci t is: 7.3 Denci Egy y 2 R V n "-fedi az f 2 V V n fggvnyt, ha (1 ; ") X fjy (x)j : x 2 V n  sgn y (x) = f (x)g > X n (1 + ") fjy (x)j : x 2 V  sgn y (x) 6= f (x)g Az "-feds teht azt jelenti, hogy azon pontok, amelyeken y eljelreprezentlja f -et, jyj-slyukat tekintve tbbsgben vannak a pontok kztt. (Szemben Aspnes et al approximci -denci jval, ahol darabszmra vannak tbbsgben, de a hibz pontokon jyj nagy is lehet.) )j denci nk birtokban kimondjuk Alternatvattel nket: 7.4 Ttel Egy f Boole-fggvnyre a kvetkez kt ll ts kzl pontosan az egyik teljesl: ;  f "-kzel thet S spektrltart val. ;  f "-fedhet 2n] n S spektrltart val. K ln kimondjuk ttel nk legfontosabb specilis esett: 7.5 Ttel Egy f Boole-fggvnyre a kvetkez kt ll ts kzl

pontosan az egyik teljesl: ; ;  D deg"(f )  d. D PAR f "-fedhet (n ; d)-fok polinommal. 46 Bizonyts. A bizonyts teljesen anal g ;azn]54 Ttel bizonytsval Alkalmazzuk a 74 Alternatvattelt az S = d esetben. 2 Most ttel nkbl specilis esetknt levezetj k Aspnes et al. 53 Alternatvattelt Ehhez kt lemmt bizonytunk, amelyek megvilgtjk az "-kzelts, a "-feds, illetve a gyenge s ers eljelreprezentci kapcsolatt. Az els lemma bizonytsa kerektsi, a msodik kompaktsgi jelleg. 7.6 Lemma A kvetkez kt ll ts ekvivalens: 1. f ersen eljelreprezentlhat S spektrltart val 2. Ltezik olyan 0  " < 1, amelyre f "-kzel thet S spektrltart val 7.7 Lemma A kvetkez kt ll ts ekvivalens: 1. f gyengn eljelreprezentlhat S spektrltart val 2. f minden 0  " < 1-re "-fedhet S spektrltart val A kt lemmb l s az 7.4 Ttelbl nyilvnval an kvetkezik a 53 Ttel Az 7.6 Lemma bizonytsa A ( irny

nyilvnval A ) irny bizonytshoz tegy k fel, hogy r ersen eljelreprezentlja f -et S spektrltart val c := minfjr(v)j : v 2 V ng d := maxfjr(v)j : v 2 V ng Nyilvnval , hogy az d1 r f ggvny rtkei abszolt rtkben cd1 s 1 kz esnek, teht 1 ; cd1 -kzelti f -et. 2 Az 7.7 Lemma bizonytsa Egy f Boole-f ggvnyt egy r pszeudo-Boole f ggvny pontosan akkor gyengn eljelreprezentl, ha hf jri = krk. Ekkor nyilvn minden 1-nl kisebb "-ra hf jri > " krk. Ezzel a ( irnyt belttuk A ) irny bizonytshoz tekints k az 1 l1 -normj pszeudo-Boole f ggvnyek halmazt. Ez kompakt rszhalmaza a pszeudo-Boole f ggvnyeknek az l1 -norma ltal induklt topol giban Mess k el ezt a halmazt azon pszeudo-Boole f ggvnyek lineris tervel, amelyeknek spektrltart ja benne van S -ben. Ez a lineris tr zrt rszhalmaza R V n -nek a fenti topol giban, teht a metszet is kompakt. Jellje a metszetet K K -n rtelmezz k az albbi folytonos funkcionlt: (r) := hrjf i 47 Ha r

"-fedi f -et, akkor r= krk is, teht feltehetj k, hogy az f -et fed r f ggvny K -ban van. Az, hogy f minden 0  " < 1-re "-fedhet S spektrltart val, ezek utn azzal ekvivalens, hogy supD  = 1 Ebbl viszont D kompaktsga s  folytonossga miatt kvetkezik, hogy ltezik r 2 D, amelyre hrjf i = 1. r nem azonosan 0, hiszen normja 1 Ez az r eljelreprezentlja f -et S spektrltart val 2 7.2 Az Alternatvattel alkalmazsa Most bemutatjuk az 7.5 Ttel egy alkalmazst, amely nmileg megjavtja Nisan s Szegedy megfelel eredmnynek, a 6.15 Ttelnek az OR f ggvnyre val alkalmazst. 7.8 Ttel A kvetkez kt ll ts kzl pontosan egy teljesl: 1. deg"(OR)  d 2. Ltezik olyan f egyvltoz s, n ; d fok polinom, amelyre 2f (0) > " n   X n k=0 k jf (k)j Bizonyts. A 75 Ttel szerint OR pontosan akkor nem "-kzelthet d fok polinommal, ha ltezik olyan r 2 R V n  degr  n ; d, amelyre hrjOR PARi > " krk : Feltve, hogy d  1,

lthat , hogy a keresett r-re hrjPARi = 0. Ezt kivonva az elz egyenltlensgbl: " krk < hrjPAR (1 ; OR)i = hrj1 ; ORi = 2r(;1 ;1 ::: ;1) Azt kaptuk, hogy a keresett r olyan pszeudo-Boole f ggvny, amelynek l1-normja majdnem teljesen a csupa-(;1) cscsba sszpontosul. r-et a szimmetrizci s technika szellemben 0 1 X r(x) = f @ xi + 1 A i2n] 48 2 alakban keress k, ahol f egyvltoz s polinom. Ekkor knnyen lthat an n   X n jf (k)j: krk = k=0 k f -nek ki kell elgtenie egyrszt a degf  n ; d felttelt, msrszt a kvetkez egyenltlensget: n   X n jf (k)j 2f (0) > " k=0 k A Szimmetrizci s Lemma (6.13 Lemma) trivilis kvetkezmnye, hogy a keresett r ltezse ekvivalens a megfelel paramter f egyvltoz s polinom ltezsvel, ms sz val nem nknyes vlaszts r-et ilyen specilis alakban keresni. 2 A feltteleket kielgt, lnyegben optimlis f polinom konstrukci ja K s Gza eredmnye K s], az  szves hozzjrulsval kzlj k. 7.9 Ttel (Ks

Gza) Ha n elg nagy, c  1:37, s m = cpn, akkor ltezik olyan f legfeljebb n ; m fok egyvltoz s polinom, amelyre n   X n jf (k)j 2f (0) > "(c) k=0 k ahol "(c) = ch (2c)1+ 1=2 : A bizonyts Csebisev polinomok elemi tulajdonsgat felhasznl konstrukci , s mellzz k. Ebbl az eredmnybl eddigi meggondolsaink alapjn knnyen kiszmolhat : 7.10 Ttel Ha n elg nagy, s "  0:1911, akkor 1 1 p 1 deg"(OR)  2 arch " ; 2 n: Nhny konkrt " rtkre kiszmoljuk a konstansokat: 7.11 Kvetkezmny Elg nagy n-re p deg0:2(OR)  1:0923 n p deg0:3(OR)  0:8509 n p deg0:4(OR)  0:6585 n 49 Ezek a becslsek valamivel megjavtjk Nisan s Szegedy megfelel eredmnyeit, melyek szerint 7.12 llts Elg nagy n-re p deg0:2(OR)  0:6324 n p deg0:3(OR)  0:5616 n p deg0:4(OR)  0:5477 n A 6.8 "llts ltal adott megfelel fels becslsek: 7.13 llts Elg nagy n-re p deg0:2(OR)  2:1165 n p deg0:3(OR)  1:8276 n p deg0:4(OR)  1:6210 n Megjegyezz

k, hogy nagy " rtkekre Nisan s Szegedy ttele ad jobb eredmnyt. 8. Kzelts racionlis trtfggvnyekkel Ebben a fejezetben a PAR f ggvnyt szmol 2 mlysg szintezett THRhl zatokkal foglalkozunk, amelyekkel mr tallkoztunk a a 4.5 Alfejezetben Ott a 429 "lltsban megadtunk egy konstrukci t, amely n kapuval szmolja PAR-t. Termszetes vrakozs, hogy ez optimlis a kapuk szmt tekintve az ilyen hl zatok kztt. Azonban ez az egyszernek tn llts nehznek bizonyul, mig megoldatlan. Mi most egy gyengbb lltst fogunk beltni. Ez Paturi s Saks PS] eredmnye 8.1 Ttel (Paturi-Saks) PAR nem szm that szintezett, 2 mlysg , 2 n= log n mret , poly s ly THR-hl zattal. Az eredmny nem igazn ers, a bizonyts azonban rdekes tleten alapul, amely a ksbbiekben tbb jelents eredmny BGS1]Bei3] kiindul pontjul szolglt. Ezek Ez az tlet a racionlis trtf ggvnyekkel val kzelts hasznlata A 81 Ttel ersebb, sly-megktssel nem l vltozatt azonban

nem ezzel, hanem a vletlen megszortsok m dszervel bizonytottk Impagliazzo, Paturi s Saks IPS]. 50 8.1 Kockaszeletels Egy k szb-kapunak megfelel egy hipersk, a kaput denil lineris kifejezs nullhelyeinek halmaza. Az ltalnossg megszortsa nlk l feltehetj k, hogy ez nem tartalmaz cscsot. Paturi s Saks els, sikertelennek bizonyult bizonytsi tlete a kvetkez egyszer meggyelsen alapult: 8.2 llts Egy 2 mlysg , PAR-t szmol szintezett THR-hl zat els szintjn lv kapuinak megfelel hipers kok elmetszik a V n kocka minden lt. Megjegyzs. A metszs alatt egyetlen bels pontban val metszst rt nk Bizonyts. A hiperskok R n -t konvex tartomnyokra bontjk Ha kt pont azonos tartomnyba esik, akkor a msodik szint kapu szmra egyformn viselkednek. A PAR f ggvny jellemzje, hogy a kocka szomszdos cscsain k lnbz rtkeket vesz fel. Teht a kocka szomszdos cscsai nem eshetnek azonos tartomnyba, akkor viszont van ket elvlaszt a hiperskok

kztt. Ez termszetesen elmetszi az ket sszekt let. 2 8.3 Denci Az n-dimenzi s kocka nyessi szma, N (n), azon hipers kok minimlis szma, amelyek egytt elmetszik a kocka sszes lt A fentiek szerint N (n) als becsls a 2 mlysg, PAR-t szmol THRhl zat els szintjn lv kapuinak szmra. Paturi s Saks azt sejtettk, hogy N (n) = (n), ami konstans szorz t l eltekintve optimlis becslst adott volna az eredeti krdsre. Ezt azonban nem tudtk bebizonytani, st N (n) rtkre a ksbbiekben sem sz lettek elg j becslsek. Az albbiakban sszefoglaljuk a kocka-nyessi problma jelenlegi llst. Az N (n) =? krdst elszr ONeil fogalmazta meg 1971-ben ON], majd egymst l f ggetlen l tbben is jra feltettk. N (n)  n, amit hrom alapveten k lnbz konstrukci is mutat. Ezek kz l kett trivilis, s a harmadik is egyszer. Az els az fxk = 0 : k 2 n]g hiperskcsald, azaz a kocka felez merleges hiperskjai. A msodik, az X fk (x) := xi 2+ 1 ; k ; 12 (k 2 n])

i2n] hiperskcsald, amely egymssal prhuzamos, a kockra tl s lls skokb l ll, s amellyel mr tallkoztunk a 4.29 "llts bizonytsa sorn 51 A harmadik, amelyet csak pratlan n-re denilunk, gy kaphat , ha az x1 + x2 + ::: + xb n c ; xd n e ; xd n e+1 ; ::: ; xn = 0 hiperskra alkalmazzuk az x1 ! x2 ! ::: ! xn ! x1 lineris lekpezs hatvnyait. Minthogy ezen hrom konstrukci olyan hiperskcsaldokat ad, amelyek nem cskkenthetk a kocka-nyessi tulajdonsg elvesztse nlk l, s mivel nem volt ismert ezeknl jobb konstrukci , ezrt azok a kutat k, akik feltettek az N (n) nagysgra vonatkoz krdst, egyben megkockztattk az N (n) = n sejtst is. Ez az n  3 esetben knnyen ellenrizhet, s n = = 4-re Emamy-Khansary Em] bizonytotta. Ezutn meglepetsknt hatott Paterson kvetkez konstrukci ja, amely cfolja a sejtst n = 6-ra. Alo]Sak] 8.4 llts (Paterson) A V 6 kockt nyesi az albbi hipers krendszer: y1 := +2x1 + 2x2 + 2x3 + 6x4 + 6x5 ; 8x6 y2 := ;4x1 ;

4x2 ; 4x3 + 6x4 + 6x5 ; 2x6 y3 := +6x1 + 6x2 + 6x3 + 2x4 + 2x5 ; 8x6 y4 := ;2x1 ; 2x2 ; 2x3 + 6x4 + 6x5 + 12x6 y5 := +6x1 + 6x2 + 6x3 + 2x4 + 2x5 + 16x6: 2 2 2 8.5 llts N (n) szubaddit v, azaz N (n + m)  N (n) + N (m) Bizonyts. Ha fak (x1  x2  ::: xn) : k 2 K g nyes skcsald V n-hez, s fbl (x1  x2  ::: xn ) : l 2 Lg nyes skcsald V m -hez, akkor fak (x1  ::: xn ) : k 2 K g  fbl (xn+1  xn+2  ::: xn+m ) : l 2 Lg nyes skcsald V n+m-hez. 2 8.6 Kvetkezmny N (n)   56 n Ez a legjobb ismert fels becsls N (n)-re. A legjobb ismert als becsls ONeil egy ttelnek ON] teljesen trivilis alkalmazsval ad dik. Ezt a ttelt nem bizonytjuk. 8.7 Ttel (ONeil) Egy hipers kkal a kocknak legfeljebb dn=2e ;dn=n2e lt metszhetjk el. Megjegyzs. Ez a becsls les is a fentebb denilt fb n c skra 2 A kocka leinek szmt, n2n;1-t elosztva ezzel a szmmal megkapjuk az albbi als becslst N (n)-re: 8.8 Kvetkezmny N (n) = (pn) 2 52 8.2 THR kzeltse

trtf ggvnnyel Racionlis trtf ggvnynek nevezz k kt n-vltoz s polinom hnyadost. Mindig olyan polinomokat vlasztunk neveznek, amelyek a szoksos rtelmezsi tartomnyon, V n-en nem tnnek el. #gy a racionlis trtf ggvny meghatroz egy pszeudo-Boole f ggvnyt. A trtf ggvny fokszmt mint a szmll s a nevez fokszmnak sszegt deniljuk. A 6.17 Ttel szerint egy THR-f ggvnyt ltalban nem lehet o(n) fokszm polinommal "-kzelteni Mint ltni fogjuk, racionlis trtf ggvnyekkel sokkal jobb a helyzet Az albbiakban bemutatjuk Newman New] konstrukci jt az abszoltrtk f ggvnyt kzelt kis fokszm racionlis trtf ggvnyre. p := e;1= p(x) := Y k;1 i=0 k (x + i) p(;x) Rk (x) := x pp((xx)) ; + p(;x) 8.9 Ttel (Newman) Rk egy (2k + 1) fok racionlis trtfggvny p 8x 2 ;1 1] : jjxj ; Rk (x)j  3e; k Newman ttelt nem bizonytjuk. Segtsgvel a nem tl nagy sly THRf ggvny "-kzeltsre knnyen konstrukci t adhatunk. P Legyen az f 2 THR az f

(x) = sgn ( i2n] wixi + w0) kifejezssel denilva, ahol a wi slyok egszek, s abszoltrtk-sszeg k, azaz f slya legyen u. 8.10 Ttel (Paturi-Saks) Legyen p k 2 N A fenti f kzel thet 2k + 2 ; fok racionlis trtfggvnnyel 3ue k hibval. Bizonyts. Vegy k szre, hogy V n-re megszortva f (x) = j X i2n] wixi + w0j=( X i2n] wixi + w0): Osszuk el a szmll t s a nevezt u-val. u denci ja szerint ekkor a szmll s a nevez egyarnt ;1 s +1 kztti szm lesz, ha x 2 V n. A szmll t a 8.9 Ttel szerint kzelthetj k az X Rk ( wixi + w0) i2n] 53 p 2P k + 1 fok racionlis trtf ggvnnyel, legfeljebb 3e; k hibval. A nevez ( i2n] wixi + wP 0 )=u. Feltett k, hogy ez sehol nem 0 a kockn A slyok egszek, teht j( i2n] wixi + w0 )=uj legalbb 1=u. Rk ( teht legfeljebb X wixi + w0)=(( X wixi + w0)=u) i2n] i2n] 3ue; k hibval kzelti f -et. p 2 8.3 THR-hlzatbl trtf ggvny Ha a p(x)=q(x) k-adfok racionlis trtf ggvny eljelreprezentlja az f

Boole-f ggvnyt, akkor a p(x)q(x) k-adfok polinom is eljelreprezentlja f -et. Ezt az egyszer szrevtelt kombinlva a 425 Kvetkezmnnyel a kvetkezt kapjuk: 8.11 Lemma PAR nem ersen eljelreprezentlhat n-nl kisebb fok 2 racionlis trtfggvnnyel. Most 8.10 Ttel segtsgvel, racionlis trtf ggvnnyel eljelreprezentlunk egy 2-szintes THR-hl zatot 8.12 Lemma A 2 mlysg szintezett N +1 kapus, U s ly THR-hl zat kimenete p eljelreprezentlhat N (2k + 2) fok polinommal, feltve hogy 2 ; k 3U e < 1. Bizonyts. Legyenek az els szint THR-kapuk h1 h2  ::: hN , a kimeneti THR-kapu pedig sgn g(y) := sgn ( X m2N ] wm ym + w0): Ennek slyt jellj p k u-val. Az els szint hm THR-kaput a 810 Ttel ; segtsgvel 3ue k hibval kzeltj k a h~ m 2k + 2-fok racionlis trtf ggvnnyel. A G(x) := g(h1(x) h2 (x) ::: hN (x)) f ggvnyt ezutn kzelts k a kvetkezvel: G~ (x) := g(h~ 1(x) h~ 2 (x) ::: h~ N (x)) G~ ppen N darab 2k + 2-fok racionlis trtf

ggvny lineris kombinci ja, ebbl azonnal kvetkezik, hogy legfeljebb N (2k + 2) fok. Msrszt a 54 kzelts hibja legfeljebb u-szorosa az egyes kapuk kzeltsbl ad d hip bknak, ahol u a legfels kapu slya. Az U 2 e; k < 1=3 felttel miatt teht a G~ egynl kisebb hibval kzelti G-t. G nullt l k lnbz egsz szm, teht G s G~ eljele azonos, G~ eljelreprezentlja a hl zat ltal szmtott f ggvnyt. 2 A 8.1 Ttel bizonytsa Tegy k fel, hogy egy a 81 Ttel feltteleinek eleget tev hl zat-sorozat szmolja a PAR f ggvnyt A hl zatok slya poly(n), azaz ltezik c, hogy minden n-re az n: hl zat slya legfeljebb nc. Ekkor knnyen lthat hogy ltezik olyan elg nagy c0 konstans, hogy ha k = c0 log2 n, akkor a 8.12 Lemmt alkalmazva a hl zatainkb l O(N (n) log2 n) fok racionlis trtf ggvnyeket kapunk, amelyek eljelreprezentljk a PAR f ggvnyt. Alkalmazva a 811 Lemmt ppen a bizonytand lltst kapjuk: N (n) = (n= log2 n) 2 9. Interpolci analitikus

fggvnyekkel Smolensky Smo2] nevhez fzdik egy ms jelleg ksrlet az analzis technikinak felhasznlsra bonyolultsgi als becslsekhez. Ebben a modellben C n -beli analitikus f ggvnyekkel reprezentljuk a Boole-f ggvnyt A reprezentci taln a legtermszetesebb: a reprezentl f ggvny V n-re megszortva azonos a reprezentland f ggvnnyel. A bevezetett bonyolultsgi mrtk, a dierencildimenzi ellenben nem hasonlt az eddig trgyalt mrtkekre. 9.1 A dierencildimenzi Legyen S  C n vges halmaz, s jellj k T -vel az S -bl C -be kpez f ggvnyek tert. 9.1 Denci Egy f : C n ! C analitikus fggvny dierencildimenzi- ja (rviden didimenzi ja) az S halmaz felett az f minden rend parcilis derivltfggvnyei ltal fesz tett fggvnytr S -re val megszor tsnak dimenzi ja a T trben. 9.2 Denci f : S ! C didimenzi ja a didimenzi k minimuma az sszes analitikus fggvnyeken, melyeknek S -re val megszor tsa f . 55 Alkalmazsainkban S -et V n-nek fogjuk

vlasztani, de a fogalom megrtshez lssunk egy egyszer pldt n = 1-re s S = m] ; re: Plda. Mennyi f : m] ! C didimenzi ja, ha f (k)-t a k Fibonacciszmnak vlasztjuk? Ismeretes, hogy f (k) alkalmas 1 2  c1 c2 konstansokkal c1 k1 +c2 k2 alakba rhat A c1 x1 +c2 x2 analitikus f ggvnynek tetszleges rend derivltja is ilyen alak, csak a c1 s c2 rtke vltozik. Teht az sszes derivlt benne van a x1 s x2 ltal generlt f ggvnytrben. Az f f ggvny didimenzi ja teht 2. 9.3 Denci Egy v 2 C n vektorra de niljuk az f analitikus fggvny eltoltjt a kvetkezkppen: fv (x) := f (x ; v) Most j mrtk nk egy ekvivalens denci jt adjuk. 9.4 llts A parcilis derivltak ltal T -ben fesz tett altr azonos az f sszes eltoltja ltal T -ben fesz tett altrrel. f didimenzi ja teht egyenl a z f sszes eltoltja ltal V -ben fesz tett altr dimenzi jval. A Taylor-sorfejtsen alapul egyszer bizonytst nem rszletezz k. 2 9.5 Kvetkezmny Ha tallunk k darab v 2 C

n vektort, amelyekre az fv jS fggvnyek linerisan fggetlenek, akkor az f didimenzi ja legalbb k. Ennek segtsgvel mutatunk egy konkrt Boole-f ggvnyt, amelynek nagyon nagy a didimenzi ja. 9.6 llts EQ(x) := AND((x1 x2 ) (x3 x4) ::: (xn;1 xn)) didimenzi ja legalbb 2n=2 . (S := V n) Bizonyts. Legyen f az EQ-t interpoll analitikus f ggvny Egy ! = = ("1 ::: "n=2) nulla-egy-vektorhoz deniljuk az f! eltoltat: f! (x1  x2  ::: xn) := f (x1 x2 + 2"1 x3  x4 + 2"2 ::: xn;1 xn + 2"n=2) Azt lltjuk, hogy ezek az eltoltak linerisan f ggetlenek. Tekints k V n-nek azt a rszkockjt, amelynek pros koordinti (;1)-ek. f! ezen a kockn ;1 rtket vesz fel minden tt, kivve az (1 ; 2"1 ;1 1 ; 2"2 ;1 ::: 1 ; 2"n=2 ;1) helyen. A 95 Kvetkezmnybl az llts nyilvnval 2 Smolensky-t az motivlta a denci megalkotsakor, hogy olyan mrtket keresett, amely minden szimmetrikus f ggvnyre kicsi, de bizonyos f ggvnyekre nagy

rtkeket is felvehet. 56 9.7 Ttel Szimmetrikus Boole-fggvny didimenzi ja legfeljebb n + 1 Bizonyts. A Young-ttel szerint egy szimmetrikus f ggvny k-adrend parcilis derivltjai egyenlek. Egy a kockn rtelmezett szimmetrikus f ggvny interpollhat legfeljebb n-edfok szimmetrikus polinommal Ennek pedig a Young ttel miatt csak n + 1 k lnbz parcilis derivltja van, hiszen az n-nl magasabb rend derivltak azonosan nullk. 2 9.2 SY MM -hlzatbl analitikus f ggvny 9.8 Ttel Egy k mret , m befok SY MM -hl zat ltal szm tott Boole-fggvny didimenzi ja (a V n halmaz felett) legfeljebb (m + 1)k . Bizonyts. Jellj k j -vel a j -dik kapu bemeneteinek sszegt Knnyen lthat , hogy a j -dik kapu kimenete interpollhat i j (x) +1 yj (x) := e m 2 egy polinomjval. Vizsgljuk meg yk parcilis derivltjt xl szerint.   @ e mi k (x) = @ 2i  (x) y k @xl @xl m + 1 k k maga is yj -k lineris kombinci ja (j < k). Ezrt a parcilis derivlst vgig elvgezve

az yj f ggvnyek szorzataib l alkotott kifejezsek lineris kombinci jt kapjuk Ez igaz marad akkor is, ha a valamelyik vltoz szerinti parcilis derivlst ismtelten elvgezz k. Ms sz val a kimeneti Boole-f ggvnyt interpolltuk egy olyan analitikus f ggvnnyel, amelyre a minden rend parcilis derivltf ggvnyek ltal fesztett f ggvnyteret a 2 +1 Yk j =1 yjdj (dj 2 N ) f ggvnyek generljk. Vegy k szre, hogy mivel j a V n halmazon csak egsz rtkeket vesz fel, ezrt minden j -re yjm+1(x) = 1 (x 2 V n) Teht a dj kitevkrl feltehetj k, hogy (m + 1)-nl kisebbek. #gy az egsz f ggvnyteret generlni tudtuk (m + 1)k f ggvnnyel. &ppen ezt akartuk bizonytani. 2 57 Az als s a fels becsls trivilis kombinlsval a kvetkez ttelt kapjuk: 9.9 Ttel (Smolensky) Az EQ Boole-fggvnyt szm t , m befok SY MM -hl zat mrete (n= log m). 2 10. Ksznetnyilvnts A szerz a legk lnbzbb okokb l ksznetet mond Antal Klmnnnak, Kirly Zoltnnak, Tardos Gbornak,

Katona Gyulnak, Frank Andrsnak, Hdvgi Zoltnnak, ifj. Antal Klmnnak, Fleiner Balzsnak, Wiener Gbornak, de legfkppen Friedl Katalinnak s K s Gznak Irodalom Aj] All] M. Ajtai 11 -formulae on nite structures Annals of Pure and App- lied Logic, 24:1-48, 1983. E. Allender A note on the power of threshold circuits In Proc 30th FOCS, pp. 580-584, 1989 AH] E. Allender, U Hertrampf On the power of uniform families of constant depth threshold circuits. In Proc 15th International Symp on Math. Foundations of Computer Science, pp 158-164, 1990 Alo] N. Alon Szemlyes Beszlgets ABFR] J. Aspnes, R Beigel, M Furst, S Rudich The expressive power of voting polynomials. In Proc 23rd STOC, pp 402-409, 1991 Bei1] R. Beigel The Polynomial Method in Circuit Complexity In Proc 8th Structure, pp. 82-95, 1993 Bei2] R. Beigel Perceptrons, PP, and the polynomial hierarchy In Proc 7th Structures, pp. 14-19, 1992 Bei3] R. Beigel When do extra majority gates help? polylog(n) majority

gates are equivalent to one. In Proc 24th STOC, pp 450-454, 1992 BGS1] R. Beigel, N Reingold, D Spielman PP is closed under intersection In Proc 23th STOC, pp 1-9, 1991 58 BGS2] R. Beigel, N Reingold, D Spielman The perceptron strikes back. In Proc 6th Structures, pp 286-291, 1991 BI] M. Blum, R Impagliazzo Generic oracles and oracle classes In Proc 28th FOCS, pp. 118-126, 1987 Bru] J. Bruck Harmonic analysis of polynomial threshold functions SIAM J. of Discrete Math, 3(2):168-177, May 1990 BS] J. Bruck, R Smolensky Polynomial threshold functions, AC 0 functions and spectral norms. SIAM J of Discrete Math, 21:33-42, 1992. Chv] V. Chvatal Linear Programming W H Freeman and Company, 1983. Cla] A. Clarke A megismers ptkvei, Osiris, Budapest, 1996 Em] M. R Emamy-Khansary On the cuts and the cut number of the 4-cube. Journal of Combinatorial Theory Series A, 41:221-227, 1986 FSS] M. Furst, J B Saxe, M Sipser Parity, circuits, and the polynomial-time hierarchy. Math

Systems Theory, 17(1):13-27, 1984 GHR] M. Goldmann, J Hstad, A A Razborov Majority gates vs general weighted threshold gates. In Proc 7th Structures, pp 2-13, 1992. GK] M. Goldmann, M Karpinski Simulating threshold circuits by majority circuits. In Proc 25th STOC, pp 551-560, 1993 Got] C. Gotsman On boolean functions, polynomials and algebraic threshold functions Manuscript, 1992 HMPSG] A. Hajnal, W Maas, P Pudlak, M Szegedy, G Turan Threshold circuits od bounded depth. In Proc 28th FOCS, pp 99110, 1987 Ha] J. Hstad Almost optimal lower bounds for small depth circuits In Advances in Computing Research 5: Randomness and Computation, pp. 143-170, JAI Press, Greenwich, CT, 1989 IPS] R. Impagliazzo, M Paturi, M Saks Size-depth trade-os for threshold circuits. In Proc 25th STOC, pp 541-550, 1993 59 KVVY] R. Kannan, H Venkateswaran, V Vinay, A C Yao A circuit-based proof of Todas Theorem. Inf & Comp, 1993 Kar] M. Karchmer On proving lower bounds for circuit size In Proc

8th Structure, pp. 112-118, 1993 KL] R. M Karp, R J Lipton Some connections between nonuniform and uniform complexity classes. In Proc 12th STOC, pp 302-309, 1980. K s] Ks Gza. Szemlyes Beszlgets LMN] N. Linial, Y Mansour, N Nisan Constant depth circuits, fourier transforms and learnability In Proc 30th FOCS, pp 574-579, 1989. MCP] W. S McCulloch, W Pitts A logical calculus for the ideas immanent in nervous activity. Bull of Math Biophysics, 5:115-133, 1943. MP] M. Minsky, S Papert Perceptrons MIT Press, Cambridge, Mass, 1969. Expanded edition, 1988 New] D. J Newman Rational approximation to jxj Michigan Math Journal, 11:11-14, 1964 Nis] N. Nisan The communication complexity of threshold gates Manuscript, 1993 Nis2] N. Nisan CREW PRAMs and decision trees In Proc 21th STOC, pp. 327-335, 1989 NS] N. Nisan, M Szegedy On the degree of boolean functions as real polynomials. In Proc 24th STOC, pp 462-467, 1992 ON] P. ONeil Hyperplane cuts of an n-cube Discrete Math,

1:193-195, 1971. Pat] R. Paturi On the degree of polynomials that approximate symmetric boolean functions In Proc 24th STOC, pp 468-474, 1992 PS] R. Paturi, M Saks On threshold circuits for parity In Proc 31st FOCS, pp. 397-404, 1990 60 Ra] A. A Razborov Lower bounds for the size of circuits of bounded depth with basis f^ g. Math Notes of the Academy of Sciences of the USSR, 41:(4):333-338, September 1987. Ra2] A. A Razborov Lower bounds for the monotone complexity of some Boolean functions. Soviet Math Dokl, 31:354-357, 1985 RR] A. A Razborov, S Rudich Natural Proofs In Proc 26th STOC, pp. 204-213, 1994 Riv] T. J Rivlin Chebyshev Polynomials Wiley and Sons, 2nd edition, 1990. Sak] M. Saks Slicing the hypercube Manuscript Sip] M. Sipser Lecture notes on Compexity Theory Manuscript Smo] R. Smolensky Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc 19th STOC, pp 77-92, 1987 Smo2] R. Smolensky On interpolation by analytic

functions with special properties and some weak lower bounds on the size of circuits with symmetric gates. In Proc 31th FOCS, pp 628-631, 1990 Sze] M. Szegedy Algebraic Methods in Lower Bounds for Computational Models with Limited Computations PhD thesis, The University of Chicago, 1989. Tar1] J. Tarui Degree complexity of Boolean functions and its applications to relativized separations In Proc 6th Structures, pp 382-390, 1991. Tar2] J. Tarui Probabilistic polynomials, AC 0 functions, and the polynomial-time hierarchy Theoretical Computer Science, pp 167-183, 1993. To] S. Toda PP is as hard as the polynomial hierarchy SIAM Journal on Computing, 20(5):865-877, 1991. VV] L. G Valiant, V V Vazirani NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85-93, 1986 Wig] A. Wigderson The fusion method for lower bounds in circuit complexity, Manuscript, 1993 61 Y] A. C Yao Separating the polynomial-time hierarchy by oracles In Proc. 31th FOCS, pp 1-10,

1985 62