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.