next up previous contents
Next: Ramsey-gráf konstrukciók és megszorított Up: Motiváció és irodalmi áttekintés Previous: Kommunikációs játékok

Eredményeink a bonyolultságelmélet köréből

A [22] cikkben megmutattuk, hogy a BNS alsó becslés a GIP függvény többrésztvevős kommunikációs bonyolultságára lényegében optimális. Pontosabban, mutattunk egy k-résztvevős protokollt, amely

\begin{displaymath}(2k-1)\left\lceil{n\over {2^{k-1}-1}}\right\rceil\end{displaymath}

bit kommunikációval számolta ki a GIP függvényt, tehát a GIP függvényre vonatkozó (3) alsó becslés lényegesen nem javítható, azaz semmiképpen sem lehet logaritmikusnál több játékosra $n^{\Omega(1)}$ alsó becslést adni.

Nagyon fontos lenne egy explicit függvény k-résztvevős kommunikációs bonyolultságára olyan alsó becslést adni, amely nem csökken exponenciálisan a k növekedésével. Például, ha sikerülne $\Omega(n/k^5)$ alsó becslést adni egy explicit (2) függvény bonyolultságára, akkor Hstad és Goldmann módszerének [33], valamint Yao [54] és Beigel és Tarui [11] tételének ötvözésével meg tudnánk mutatni, hogy az illető g függvény nem számolható ki ACC-ben, azaz korlátos mélységű, polinomiális méretű, $\hbox{\rm MOD}_m$ kapukat is tartalmazó hálózat-sorozattal. Sajnos, azonban, az ilyen ``nagy'' alsó korlát bizonyítására történt erőfeszítések eddig kudarcot vallottak.

A [27] cikkben megmutattuk, hogy minden olyan három mélységű hálózat, amely tetején egy THRESHOLD kapu foglal helyet, alatta tetszőleges szimmetrikus kapuk vannak, és legalul pedig k-bemenetű $\hbox{\rm MOD}_m$ kapuk foglalnak helyet, csak exponenciálisan sok kapuval tudja kiszámolni a k-oszlopos GIP függvényt, feltéve, hogy az m modulusra teljesül, hogy páratlan szám, és $m\equiv k \bmod 2m$. Megjegyezzük, hogy ha az alsó kapuk bemenete k-1 lenne, akkor a Hstad és Goldmann módszeréből [33] rögtön adódna az állítás. A bizonyítás lelke egy több-résztvevős kommunikációs játék.

A [24] cikkben elválasztási eredményeket bizonyítottunk prím- es nem-prímhatvány modulusú moduláris hálózatok többrésztvevős kommunikációs bonyolultsága között. Azt mutattuk meg, hogy a nem-prímhatvány-modulusú moduláris hálózatok által kiszámolt függvények többrésztvevős kommunikációs bonyolultsága sokkal nagyobb, mint a prím-modulusú hálózatok által kiszámolt függvényeké.

A [23] cikkben (folyóirat-változata [29]), azt mutattuk meg, hogy azok a háromszintű hálózatok, amelyek tetején egy THRESHOLD kapu van, a következő szinten ÉS kapuk, majd a legalsón pedig tetszőleges be-fokú $\hbox{\rm MOD}_m$ kapuk helyezkednek el, csak exponenciálisan sok kapuval tudják kiszámítani a belső szorzat mod 2 függvényt, amelyet a következőképpen definálunk:

\begin{displaymath}{\rm IP}(x_1,x_2,\ldots,x_n;y_1,y_2,\ldots,y_n)=\sum_{i=1}^n x_iy_i \bmod{2}.\end{displaymath}

Ez az eredmény azért fontos, mert a hálózatban nem szorítottuk meg a be-fokot egyik szinten sem. Érdekes megjegyezni, hogy ha a MOD kapuk nem a hálózat alján, hanem a tetején foglalnak helyet, akkor már egy lineáris méretű hálózat is ki tudja számolni az IP függvényt. Valóban, tekintsük a MOD 2 tetejű, és n darab ÉS kaput tartalmazó, n+1 méretű, kettő mélységű hálózatot, ha az i. ÉS kapu bemenete xi és yi, akkor a kimenet nyilván az IP függvény értéke. Ezeket az eredményeinket tovább általánosította cikkében Beigel és Maciel [10].

A Boole-függvények Fourier-kifejtését ([38], [12], [34], [44]) a következőképpen definiáljuk: Reprezentáljuk az f Boole-függvényt mint $f:\{-1,1\}^n\to \{-1,1\}$ ahol is -1 jelenti az ``igaz'' logikai értéket. A $\{-1,1\}^n$ értelmezési tartományú valós függvények 2n dimenziós vektorteret alkotnak a valós számok felett. Az $\alpha=(\alpha_1,\alpha_2,...,\alpha_n)\in\{0,1\}^n$ jelöléssel definiálhatjuk az $x^\alpha$ monómot:

\begin{displaymath}x^\alpha=\prod_{i=1}^nx_i^{\alpha_i}.\end{displaymath}

Az $x^\alpha$ monómok az $\alpha\in\{0,1\}^n$ multi-indexekre ezen 2n-dimenziós vektortér egy bázisát alkotják, így tetszőleges $h:\{-1,1\}^n\to{\bf R}$ függvényt egyértelműen felírhatunk mint

\begin{displaymath}h(x_1,x_2,...,x_n)=\sum_{\alpha\in\{0,1\}^n}a_\alpha x^\alpha.\end{displaymath}

A fenti kifejezés jobb oldala a h Fourier-kifejtése, és a $a_\alpha$ számok pedig $\alpha\in\{0,1\}^n$-ra a h Fourier-együtthatói. A h ${\rm L}_1$ normájának definíciója:

\begin{displaymath}{\rm L}_1(h)=\sum_{\alpha\in\{0,1\}^n}\vert a_\alpha\vert.\end{displaymath}

A [30] és a [26] cikkekben azt mutatjuk meg, hogy a kis L1 normájú Boole-függvények egyes kommunikációs modellekben ``könnyen'' kiszámíthatók. Pontosabban, a [26] cikkben megadunk egy $O(\hbox{\rm L}^2_1\delta)$ bitet használó kétjátékosú, common-coin, véletlen protokollt, amelynek hiba-valószínűsége csak $\exp(-c\delta)$, valamely pozitív c-re. Tehát a protokoll által kommunikált bitek száma csak a függvény $\hbox{\rm L}_1$ normájától függ, még exponenciálisan sok nem-0 Fourier-együtthatót tartalmazó Fourier-kifejtésre is. Ennek az eredménynek több alkalmazását találtuk az IP függvény (mint nagy véletlen kommunikációs-bonyolultságú függvény) tetszőleges mélységű, és korlátos mélységű hálózati bonyolultságának becslésére, valamint az IP függvény döntési fa bonyolultságának alsó becslésére is. Többek közt megmutattuk, hogy ha a 2n bemenetű IP függvényt egy kettő mélységű hálózat számolja ki, amelynek a tetején egy MAJORTY kapu van, alatta pedig olyan kapuk, amelyek -- valamely $\nu<1/2$-re -- az inputnak legfeljebb $n^\nu, $ $\hbox{\rm L}_1$-normájú függvényeit számolják ki, akkor a hálózat mérete exponenciális kell, hogy legyen. Eredményeink párhuzamba állíthatók Nisan [43] eredményeivel, aki hasonló állításokat bizonyított kis $\hbox{\rm L}_1$ normájú kapuk, illetve (döntési fák esetében) tesztfüggvények helyett kisfokú polinommal reprezentálható kapukra, illetve tesztfüggvényekre.

A Lovász-Saks sejtés (1) egy, a többváltozós kommunikációs játékokra vonatkozó analógiáját bizonyítottuk be a [30] cikkben. Azt mutattuk meg, hogy egy tetszőleges f Boole függvényt ki tudunk számolni az f $\hbox{\rm L}_1$ normájában poli-logaritmikus számú bit kommunikációjával, feltéve, hogy legalább $k=c\log\hbox{\rm L}_1(f)$ játékos vesz részt a protokollban. A bizonyítás Bruck és Smolensky egy eredményét [12], valamint egy többrésztvevős protokoll konstrukciót használ fel, és tudomásunk szerint ez az első (és eddig egyedüli) olyan eredmény, amely általános Boole-függvények többrésztvevős kommunikációs bonyolultságára ad nem-triviális felső korlátot.

A [28] cikkben bebizonyítottunk egy fontos Fokcsökkentő Lemmát. Megmutattuk, hogy ha q és p különböző prímek, akkor azok a kettő mélységű $\hbox{\rm MOD}_q\circ\hbox{\rm MOD}_p$ hálózatok, amelyek inputja a változókból szerkesztett tetszőleges d. fokú polinomja, helyettesíthetők ugyancsak kettő mélységű $\hbox{\rm MOD}_q\circ\hbox{\rm MOD}_p$ hálózatokkal, amelyek inputja a változók lineáris polinomja (ld. az 2.2.1. ábrát). Ha az eredeti hálózat input-polinomja d szorzással állítható elő lineáris tagokból, akkor az utóbbi, lineáris polinomokat tartalmazó hálózat mérete az eredetinek legfeljebb p2d-szerese lesz. Ezen észrevétel segítségével bizonyítottuk Barrington, Beigel és Rudich [8] Konstans Fok Sejtésének fontos speciális esetét. Megjegyezzük, hogy Fokcsökkentő Lemma nem teljesülhet a $\hbox{\rm MOD}_q\circ\hbox{\rm MOD}_q$ esetben, mint ahogy azt az előző fejezet Példájából következik, hiszen az ilyen hálózatok az input egy konstans fokú polinomját számítják ki tetszőleges méret esetén, amíg a $\hbox{\rm MOD}_q\circ\hbox{\rm MOD}_p$ hálózatokban a nagyobb mérethez tartozhat nagyobb fokú output-polinom a q elemű test felett.

 
Figure: Fokszám-csökkentés a $\hbox{\rm MOD}_3\circ\hbox{\rm MOD}_2^{\{1\}}$ esetben. A bal oldalon az input másodfokú polinom, a jobboldalon pedig lineáris polinomokból áll. Mindkét hálózat ugyanazt a függvényt számolja ki.
\begin{figure}
\centerline{{\psfig{figure=circebb.ps,height=6cm,width=14cm}}}\end{figure}

A Tardos Gáborral közös [31] cikkben általánosítottuk a fenti Fokcsökkentő Lemmát, és egy új véletlen klaszterezési eljárást is bevezettünk $\hbox{\rm MOD}_q\circ\hbox{\rm MOD}_p$ tetejű hálózatok számítási erejének becslésére. A klaszterezési eljárás csak lineáris polinomokból álló bemenetű $\hbox{\rm MOD}_q\circ\hbox{\rm MOD}_p$ hálózatokra alkalmazható; azonban, ha nincs túl sok nagy-fokú tag az input-szinten levő polinomban, akkor eredményesen linearizálhatunk a Fokcsökkentő Lemmával. Ha ez a módszer nem alkalmazható már közvetlenül, akkor, ha még a módszerünk alkalmazása előtt egy alkalmasan megválasztott véletlen megszorítást hajtunk végre az input-változókon, akkor az input-polinom magasfokú tagjai számának csökkentése után már lehet erős alsó korlátokat bizonyítani. A módszerrel sikerült további fontos speciális eseteit bizonyítani Barrington, Beigel és Rudich [8] Konstans Fok Sejtésének. Talán érdemes megemlíteni a következő eredményünket: Legyen q egy prím, m, $\alpha$ és d pozitív egészek, C pedig egy olyan, az n bemenetű ÉS függvényt kiszámoló $\hbox{\rm MOD}_{q^\alpha}\circ\hbox{\rm MOD}_m\circ{\rm AND}_d$ hálózat-sorozat, amelyre teljesül, hogy a $\hbox{\rm MOD}_m$ kapuk be-foka $o(n^2/\log n)$. Ekkor a hálózatok mérete szuper-polinomiális n-ben (exponenciálisra nő az alsó korlát, ha a $\hbox{\rm MOD}_m$ kapuk be-foka csupán $n^{2-\varepsilon})$.


next up previous contents
Next: Ramsey-gráf konstrukciók és megszorított Up: Motiváció és irodalmi áttekintés Previous: Kommunikációs játékok
Vince Grolmusz
1999-11-08