next up previous contents
Next: Kommunikációs játékok Up: Motiváció és irodalmi áttekintés Previous: Motiváció és irodalmi áttekintés

Boole-hálózatok

Cook 1971-es STOC előadásán [14] vezette be az NP-teljesség fogalmát, és ugyanott bizonyította, hogy a SAT nyelv NP-teljes. Ez az eredmény irányította sok kutató figyelmét a P és az NP nyelvosztályok viszonyának tanulmányozására. Sok ünnepelt eredmény, szép elmélet és igen tekintélyes erőfeszítések ellenére még ma sem tudunk egy NP-beli nyelv számítási bonyolultságára sem lineárisnál jobb alsó időkorlátot adni, holott annak megmutatásához, hogy az L nyelv nincs a P osztályban azt kellene igazolni, hogy a $w\in L$ kérdés eldöntéséhez nem elég |w|O(1) lépés.

A nyolcvanas évek közepén több, a kérdés iránt érdeklődő kutató figyelme a Boole-hálózatok felé fordult. Ennek egyik magyarázata a következő észrevétel: tegyük fel, hogy a $w\in L\subset \{0,1\}^*$ kérdést eldönti egy T Turing-gép polinomiális idő alatt. Ekkor létezik egy c>0 konstans és egy $C_n, n=1,2,\ldots$ Boole-hálózat sorozat (mondjuk - kissé redundánsan - az $\lnot$, $\land$ és az $\lor$ kapukkal), amelyre teljesül az, hogy tetszőleges $w\in \{0,1\}^*$ esetén C|w| eldönti, hogy w L-ben van-e, vagy sem, és Cn mérete nem nagyobb, mint nc [51].

Ha sikerülne megmutatni, hogy egy NP-beli nyelvre ilyen polinomiális méretű hálózat-sorozat nem létezik, akkor ebből már következne, hogy P$\ne$NP. Megjegyezzük, hogy azt igen könnyű bizonyítani, hogy a Boole-függvények majdnem mindegyikének kiszámításához exponenciális méretű Boole-hálózat szükséges [51].

Nagy meglepetést okozott Razborov [48] eredménye 1985-ben, amelyben szuper-polinomiális alsó korlátot sikerült bizonyítani a CLIQUE nyelvet kiszámoló monoton hálózati bonyolultságra, ahol a monoton azt jelenti, hogy a Boole-hálózatban csak a $\land$ és a $\lor$ kapuk vannak megengedve. Az alsó becslést hamarosan Andreev [3] javította exponenciálisra. Az - egyáltalán nem triviális - eredményt követő euforikus hangulatban sok kutató abban bízott, hogy Razborov módszerének és néhány új ötletnek a kombinálásával a P$\ne$NP állítás bizonyítására már csak néhány hónapot kell várni. Azonban hamarosan kiderült - Razborov maga bizonyította be [47] -, hogy P-ben levő monoton problémák esetében is előfordulhat, hogy az azt kiszámoló monoton Boole-hálózat mérete legalább szuper-polinomiális, tehát Razborov módszerétől nem várható, hogy NP-t és P el tudjuk választani egymástól.

Ezután, mivel reménytelennek látszott a nem-monoton általános Boole-hálózatokra vonatkozó alsó becslési technikák kidolgozása, sokan kezdték el vizsgálni azokat a hálózatokat, amelyek mélységére tettünk megszorítást. A fő kérdés itt is az volt, hogy mely függvények számíthatók ki korlátos mélységű, polinomiális méretű hálózatokkal. Ezeknek a vizsgálatoknak a párhuzamos számítógépek elméletében is jelentős szerepük van, hiszen a hálózat mélysége megfelel a párhuzamos időnek. Nagyjelentőségű lenne olyan P-beli nyelv megtalálása, amelynek felismerésére nem létezik poli-logaritmikus (azaz $\log^{O(1)}n$) mélységű, polinomiális méretű Boole-hálózat sorozat. Ez az eredmény azt mutatná, hogy nem minden P-beli nyelv ismerhető fel hatékonyan párhuzamosan, azaz elválasztaná egymástól a P és az NC osztályokat.

Furst, Saxe es Sipser [19] és Ajtai [2] nevéhez fűződik az híres eredmény, amely szerint legalább szuper-polinomiálisan sok $\land$, $\lor$ és $\lnot$ kapura van szükség egy, a PARITY (azaz a mod 2 összeadás) függvényt konstans mélységben kiszámító hálózatban. Furst, Saxe és Sipser módszerét jelentősen javította híres cikkében Yao [53], akinek sikerült exponenciális alsó becslést megadni, majd a bizonyítást tovább javította és egyszerűsítette Hstad [32]. Az utóbbi két eredményből az is következik, hogy ha egy polinomiális méretű Boole-hálózat sorozat kiszámolja az n bemenetű PARITY függvényt, akkor legalább

\begin{displaymath}\Omega\left({\log n \over \log \log n}\right)\end{displaymath}

mélységűnek kell lennie. Megjegyezzük, hogy olyan technikák máig sem ismertek, amelyekkel ezeknél mélyebb, nem-monoton hálózatok méretére nemtriviális alsó korlátokat lehetne adni.

A fenti eredmények azt mutatták, hogy a PARITY függvényt ``nehéz'' kiszámolni korlátos mélységű, csak $\land$, $\lor$ és $\lnot$ kapukat tartalmazó hálózatokkal. Felmerült a kérdés, hogy mennyivel lesz erősebb a számítási modellünk, ha - kapuként - megengedjük a ``nehéz'' PARITY használatát is?

Razborov [49] megmutatta, hogy a MAJORITY függvény (amelyet úgy definiálunk, hogy értéke megegyezik az inputban többségben levő bit értékével) kiszámításához még a PARITY kapu felhasználásával is exponenciálisan sok kapu kell konstans mélységben. 2.1

A következő kérdés feltevése ugyancsak természetes volt: Mi a helyzet, ha nem csak 2-vel való oszthatóságot vizsgáló kaput, a PARITY kaput, hanem az m pozitív egész számmal való oszthatóságot vizsgáló kaput engedünk meg? Vagy még általánosabban, definiáljuk a következő kaput:

\begin{displaymath}\hbox{\rm MOD}^A_m(x_1,x_2,\ldots,x_n)=\cases{1, \hbox{ ha } \sum_{i=1}^nx_i \bmod{m}\in A\cr
0 \hbox{ egyébként.}}\end{displaymath}

Smolensky [50] talált egy nagyon szép módszert annak megmutatására, hogy ha a $\land$, $\lor$ és $\lnot$ kapukon kívűl még $\hbox{\rm MOD}^A_m$ kapukat is megengedünk, ahol $m=p^\alpha$, valamely p prímre és $\alpha$ természetes számra, akkor a MAJORITY vagy a $\hbox{\rm MOD}^{\{0\}}_q$ kiszámítása exponenciálisan sok kaput igényel konstans mélységben, ahol q prím, és $q\ne p$.

A fenti eredmények nyitva hagyják azt a természetes -- és sokak által (Barrington, Simon, Smolensky) -- csaknem egyidőben, 1985-86-ban feltett kérdést, hogy mi számítható ki akkor, ha a kapuk között megengedjük a $\hbox{\rm MOD}^A_m$ kapukat is, ahol az m nem-prímhatvány, összetett szám, például 6. A kérdés megválaszolásával sokan és hosszú idő óta foglalkoznak, jelentős eredmények is születtek, de jelenleg még mindig nagyon keveset tudunk a $\hbox{\rm MOD}_6$ kapuk számítási erejéről. A helyzetet jól szemlélteti az - ezen tézisek irásának időpontjában legjobb tudásunk szerint érvényes - alábbi megállapítás:


Jelenlegi tudásunkkal konzisztens lenne egy olyan eredmény, amely szerint az olvasó kedvenc NP-teljes nyelve felismerhető egy, az inputban lineáris méretű, 2 mélységű, csak MOD 6 kapukat tartalmazó hálózat-sorozattal.


A kudarc fő oka az lehet, hogy a prím-modulusok esetében rendelkezesre álló algebrai technikák összetett modulosokra nem alkalmazhatóak. A másik - talán kevéssé valószínű, de ki nem zárható - ok az lehet, hogy az összetett, nem-prímhatvány modulusú kapuk tényleg jelentősen erősebbek, mint a prím-, vagy prímhatvány-modulusok.

A $\hbox{\rm MOD}_6$ kapuk erejét az alábbi példa mutatja:

Példa
Könnyű látni [50], hogy ha m=p prím, akkor $\hbox{\rm MOD}^A_m(x_1,x_2,\ldots,x_n)$ az input változóinak p-1-ed fokú polinomja a p elemű test felett. Legyen $\cal C$ egy d mélységű Boole-hálózat, amelyben csak $\hbox{\rm MOD}_p$ kapuk vannak. Ekkor tehát az egész hálózat egy (p-1)d. fokú polinomját számolja ki az input változóknak.


Másrészt viszont az $f:\{0,1\}^n\to {\rm GF}_p$ függvények 2n dimenziós vektorterének az $x_I=\prod_{i\in I}x_i,\ I\subset \{1,2,\ldots,n\}$ monómok egy bázisát alkotják, tehát minden $f:\{0,1\}^n\to {\rm GF}_p$ függvény egyértelműen állítható elő monómok lineáris kombinációjaként. Az n változós VAGY függvény előáll:

\begin{displaymath}1-\prod_{i=1}^n (1-x_i)\end{displaymath}

alakban. Ennek a foka n, tehát csak n-nél kisebb fokú monómok lineáris kombinációjaként nem áll elő. Tehát beláttuk, hogy ha egy d mélységű, csak MODp kapukat tartalmazó Boole-hálózat kiszámolja az n változós VAGY függvényt, akkor $d\geq \frac{n}{p-1}.$


Tehát konstans mélységű, MODp kapukból álló Boole-halózat nem tud kiszámolni egy olyan egyszerű függvényt, mint az n változós VAGY, sőt, igazából ehhez lineáris mélység kell. Ha azonban $\hbox{\rm MOD}_p$ kapuk helyett MOD6 kapukat használunk fel, akkor már egy kettő mélységű Boole-hálózattal ki tudjuk számítani a logikai VAGY függvényt ([35], [9]), az alábbi módon:


Vegyük először észre, hogy egy MOD6 kapuval MOD2 és MOD3 kapukat is tudunk szimulálni, egyszerűen a változókhoz menő élek háromszorozásával, illetve kétszerezésével:

\begin{displaymath}\hbox{\rm MOD}_3^{\{1,2\}}(x_1,x_2,\ldots,x_n)=\hbox{\rm MOD}_6^{\{1,2,3,4,5\}}(2x_1,2x_2,\ldots,2x_n)\end{displaymath}


\begin{displaymath}\hbox{\rm MOD}_2^{\{1\}}(x_1,x_2,\ldots,x_n)=\hbox{\rm MOD}_6^{\{1,2,3,4,5\}}(3x_1,3x_2,\ldots,3x_n)\end{displaymath}

Ezek után tekintsük a következő $\hbox{\rm MOD}^{\{1,2\}}_3\circ\hbox{\rm MOD}^{\{1\}}_2$ hálózatot: A változók feletti szinten 2n darab $\hbox{\rm MOD}^{\{1\}}_2$ kapu van, a $\{x_1,x_2,\ldots,x_n\}$ halmaz minden részhalmaza pontosan egy $\hbox{\rm MOD}^{\{1\}}_2$ kapunak az inputja. A hálózat tetején pedig egyetlen $\hbox{\rm MOD}^{\{1,2\}}_3$ kapu van. Ha $x_1=x_2=\cdots=x_n=0$, akkor minden $\hbox{\rm MOD}^{\{1\}}_2$ kapu kimenete 0, és az egész hálózat kimenete is 0. Ha azonban néhány xi=1, akkor a $\hbox{\rm MOD}^{\{1\}}_2$ kapuk pontosan fele lesz összekötve páratlan sok egyest tartalmazó inputtal, tehát pontosan 2n-1 kapu ad 1-es outputot. Ez a szám viszont nem osztható hárommal, tehát a hálózat tetején levő kapu is egyes inputot ad. Tehát egy exponenciális méretű, kettő mélységű $\hbox{\rm MOD}_6$ kapukból álló hálózat ki tudja számolni a VAGY függvényt.

Barrington, Straubing és Thérien [9] megmutatta, hogy a fenti konstrukció olyan értelemben optimális, hogy ha a VAGY függvényt akarjuk kiszámolni kettő mélységű $\hbox{\rm MOD}_p\circ\hbox{\rm MOD}_q$ hálózattal (p,q prím), akkor exponenciális méretre mindenképpen szükségünk van. Az alkalmazott algebrai technikák sajnos nem használhatóak arra az esetre, amikor a hálózat tetején egyetlen, nem-prímhatvány, összetett modulusú kapu van.

Barrington, Straubing és Thérien [9] Konstans Fok Sejtése (CDH) szerint az exponenciális alsó korlát akkor is teljesül, ha az input-szinten a változók d. fokú polinomjait is megengedjük.

Meg kell említeni még Krause és Waack [36] eredményét, amelyben a szerzők megmutatták, hogy a kettő mélységű $\hbox{\rm MOD}^{\{1,2,\ldots,m-1\}}_m\circ\hbox{\rm MOD}_m^A$ hálózatok -- tetszőleges m-re -- exponenciális mérettel kell, hogy rendelkezzenek, ha az

\begin{displaymath}\hbox{\rm ID}(x,y)=\cases{1,\hbox{ if } x=y,\cr
0 \hbox{ egyébként,}}\end{displaymath}

függvényt számolják ki. Az alkalmazott technikák sajnos csak a nagyon speciális tetőn elhelyezkedő $\hbox{\rm MOD}^{\{1,2,\ldots,m-1\}}_m$ kapura működnek, azaz erősen kihasználják azt a tényt, hogy egy olyan függvényt kell kiszámolni, amely az input túlnyomó többségén 0, egy olyan felső kapuval, amely a legtöbb inputra 1.

Fontos visszavezetést tett Yao [54], majd ezt az eredményt javítva és egyszerűsítve Beigel es Tarui [11], akik megmutatták, hogy ha egy függvény kiszámítható egy konstans mélységű, polinomiálisan sok $\hbox{\rm MOD}_m$, valamint $\land$, $\lor$ és $\lnot$ kaput tartalmazó hálózattal (röviden ezeket a hálózatokat ACC-hálózatoknak is hívják) akkor szintén kiszámolható egy kettő mélységű, $\exp(\log^{O(1)}n)$ méretű olyan hálózattal is, ahol a hálózat tetején egy szimmetrikus függvényt kiszámoló kapu foglal helyet, alatta pedig ÉS kapuk vannak, mindegyik legfeljebb $\log^{O(1)}n$ inputtal, vagy az input negációjával van összekapcsolva.

Ez az utóbbi eredmény a kutatókat a fenti, kettő mélységű hálózatra való alsó becslések kidolgozására sarkallta, eddig, sajnos, nem sok sikerrel. Egy lehetséges módszer a kommunikációs játékokat használja az ilyen és hasonló hálózatokra való alsó becslések kidolgozására, valamint a már említett Krause-Waack [36] eredményt is lényegileg a kommunikációs játékok motiválták. Mivel saját eredményeink jelentős részét is kommunikációs játékok segítségével értük el, ezért röviden áttekintjük az ide tartozó definíciókat és eredményeket.


next up previous contents
Next: Kommunikációs játékok Up: Motiváció és irodalmi áttekintés Previous: Motiváció és irodalmi áttekintés
Vince Grolmusz
1999-11-08