Bonyolultságelmélet szeminárium

2014 Tavasz

Vezetők: Grolmusz Vince, Friedl Katalin, Pálvölgyi Dömötör, Király Zoltán

Minden második héten, Szerda 10:15-13:00
Pázmány Péter sétány 1/C. 3.607


Hirdetmények


Ajánlott irodalom


1. alkalom (II. 19.) CIKKOSZTÁS


2. alkalom (III. 5.) Mészáros András

"Yao-Hastad tétel"

Fő célunk annak megmutatása lesz, hogy a paritás nem számítható ki konstans mélységű polinomiális méretű hálózattal. (Vagy, hogy minél jobb alsó korlátot adjunk egy konstans mélységű hálózat méretére.)

Az egyik fontos ötlet az, hogy az alsó két szint kapuit cseréljük meg valahogy anélkül, hogy a méret nagyon nőne. Ha a csere előtt a 2. szinten ÉS kapuk voltak, akkor a csere után VAGY kapuk lesznek, így a 2. és a 3. szint VAGY kapui összeolvaszthatóak, így csökken a szintek száma.

Egy ilyen megcserélés általában exponenciálisan felnövelheti a kapuk számát. Azonban, ha néhány változónak lefixáljuk az értékét, akkor lehet, hogy már végrehajtható a csere jelentős méretnövekedés nélkül, persze az is kell, hogy elég sok szabad változónk maradjon. Ilyen jó megszorításnak a létét véletlen módszerrel fogjuk megmutatni. Mindennek azért tudjuk majd hasznát venni, mert a paritás megszorítása is paritás vagy annak negáltja.


3. alkalom (III. 19.) Kisfaludi-Bak Sándor

"Razborov-féle exponenciális alsó becslések többségre, paritásra és klikkre"

Az előadáson áttekintjük Razborov 80-as évek második felében publikált alsó becslési módszereit, illetve ezek több szerző által javított változait Boole-hálózatok méretére. Először a többség és paritás feladatokra adott módszert vizsgáljuk: látni fogjuk, hogy bizonyos nehezen számítható függvényeket - PARITY ill MOD_3 - kapuként megengedve is exponenciális méretű hálózat kell a kiszámoláshoz (konstans mélység esetén).

Ezután rátérünk a monoton Boole-függvényekre és Boole-hálózatokra. Az (n,k)-klikk feladatban az input egy n csúcsú gráf adjacencia mátrixa, és a válasz 1, ha a gráf tartalmaz k méretű klikket. Belátjuk, hogy k


4. alkalom (IV. 2.) Tóthmérész Lilla

"Kriptogenográfia"
Brody, Jakobsen, Scheder és Winkler cikke.

A kriptográfia klasszikus kérdése hogy hogyan tud néhány játékos úgy kommunikálni, hogy ők megtudják az egyikük által ismert titkot, de egy hallgatózó fél ne tudja meg. A cikk egy új típusú (de szintén a való élet által motivált) kérdést tesz fel: Tudnak-e a játékosok úgy kommunikálni, hogy mindnyájan megtudják a titkot, de egy hallgatózó fél ne tudja kitalálni hogy ki volt eredetileg a titok őrzője. Azaz szeretnénk titokban tartani hogy ki szivárogtatta ki a titkot. (És hogy a hallgatózó fél megtudja-e a titkot magát, azzal nem is foglalkozunk.) A cikk protokollokat mutat, aminek segítségével 2 játékos esetén a hallgatózó fél 1/3 eséllyel hibásan tippel a kiszivárogtató személyére, több játékos esetén pedig 0.5644 valószínűséggel. Másrészt megmutatják, hogy 2 játékos esetén az ellenséget nem lehet 3/8 -nál nagyobb valószínűséggel hibára kényszeríteni, és több játékos esetén pedig 3/4-nél nagyobbra.


5. alkalom (IV. 23.) Pálvölgyi Dömötör

"Gyenge Paritás"
Aaronson, Ambainis, Balodis és Bavarian cikke.

Az előadásban bevezetésre kerül egy újfajta döntési modell, melyben az inputok több mint felére nagy valószínűséggel jó választ kell adnunk, a többire viszont bármit. Mutatunk a PARITY-re egy O(n^0.753..)-es protokollt, valamint megmutatjuk hogyan következne egy polinomiális alsó korlát ismert sejtésekből és részletesebben megvizsgáljuk a kapcsolatukat.

Aki szeretne egy bemelegítő feladatot, az mondjon egy olyan RND protokollt, ami (x,y)\in {0,1}^2-re a 4 lehetséges inputbol 3-ra 2/3 eséllyel jól tippeli meg x+y mod 2-t, és csak 1 bitet kérdez. Azt is könnyű meggondolni, hogy a 2/3 nem javítható.


6. alkalom (V. 7.) Király Csaba

"3-SAT-ra visszavezetés gyorsan"
Jahanjou, Miles és Viola cikke.

Régóta ismert, hogy egy NTIME(T)-beli L nyelvet vissza lehet vezetni T-ben kvázilineáris hosszú 3-SAT-okra úgy, hogy adott x inputra a hozzárendelt \phi formula pontosan akkor kielégíthető, ha x L-beli. Ráadásul, ilyenkor x-hez poly(n,log T) időben megadható egy C Boole-hálózat, mely (egy i (log |\phi|)-bites indexre) az i inputon legyártja \phi i-edik klózát. A korábbi legjobb eredmény C méretére az volt hogy C NC^1-ben van, és még poly(T) méretű formulát követelve is csak AC^0-s korlát volt bizonyítható.

Most, a fenti NC^1-es eredmény egy alternatív bizonyításából kiindulva, azt lokálisan javítva kapjuk a cikk fő eredményét, hogy adható NC^0-beli C hálózat is \phi klózainak az előállítására. Ennek az eredménynek számos további érdekes következménye van.