Jelenlegi hely

Tanszékcsoporti szeminárium

Félév: 
2015/16 I. félév
Helyszín: 
Árpád tér 2. II. em. 220. sz.
Dátum: 
2015-09-29
Időpont: 
14:00-15:00
Előadó: 
Iván Szabolcs
Cím: 
Hálózati bonyolultság megszorított esetekben
Absztrakt: 
Boole-függvények családjainak reprezentálására egy jól ismert eszköz a
hálózatcsaláddal való reprezentálás. Ha minden n-re adott egy Cn
hálózat, mely egy {0,1}^n->{0,1} függvényt számít ki, beszélhetünk
arról, hogy n függvényében az egyes Cn hálózatok hány kaput tartalmaznak
ill. milyen mélyek, arról is, hogy a hálózatokban milyen kaputípusokat
engedünk meg, és arról is, hogy a hálózatcsalád uniform-e (azaz Cn
elkészíthető-e poly(n) idő alatt algoritmikusan). Ennek a területnek egy
nagy nyitott feladványa, hogy adjuk meg Boole-függvényeknek egy explicit
családját, melyek mindenképp exponenciálisan nagy hálózatokat
igényelnek. Egyszerű leszámlálással kijön, hogy a Boole-függvénycsaládok
túlnyomó többsége tényleg igényel ekkora hálózatokat, viszont a mai
napig csak lineáris alsó korlátokat sikerült bizonyítani.
Könnyebb a helyzet, amennyiben pl. csak VAGY kapukat engedünk meg a
hálózatban. Ekkor a kiszámítható Boole függvények osztálya is leszűkül
és vannak a fentinél jobb ismert alsó korlátok is.
Az előadás első felében Boole-függvények hálózati bonyolultságáról
beszélek általában, a második felében pedig az előbbi speciális esetről,
alkalmazva olyan látszólag talán távol eső eszközöket is, mint az erős
dualitási tétel, mellyel meglepő módon (majdnem) éles korlátokat is
elérhetünk.