A kommunikációs bonyolultság alapkérdésében egy függvény értéket szeretnénk kisz'amolni (x,y)-ban úgy, hogy a x és y két különbözõ ember számára ismert. Hogy feladatunkat megoldjuk a két embernek kommunikálnia kell egymással. Feltesszük, hogy x és y is két n hosszú bitsorozat. A kommunikáció alatt közvetített bitek számát mérjük és ezt szeretnénk minimalizálni.
Az alapfogalmak matematikai megfogalmazása után néhany klasszikus példát mutatok be.
Az elõadás nagyobb része Tardos Gábor és Uri Zwick, The Communication complexity of the Universal Relation címû 1997-es cikkét ismertetem. A cikk fõ kérdése, hogy a két ember számára kiadott x és y bitsorozatról tudjuk, hogy különbözõ. Céljuk egy olyan pozíció megtalálása, amelyben a két sorozat különbözik. A protokol végén mindkét résztvevõnek tudnia kell egy közös pozíciót, amely megoldja a feladatot. Mi a probléma kommunbikációs bonyolultsága?
Nem árulom el a választ. Az alapkérdése módosítható: mi a helyzet, ha elég csak az egyik résztvevõnek talánia egy megfelelõ pozíciót; és ha nem szükséges, hogy közös pozícióban állapodjanak meg; és ha az információ áramlás irányának változása csak konstans sokszor változhat?
A sok kérdésre adandó válaszokhoz nagyon
szép kombinatorikus ötletek szükségesek. Az elõadásig
mindenki gondolkozhat a felvetett kérdéseken.