Mint arrol mar szo volt korabban, a PCP tetel merfoldkonek szamitott a diszkret optimalizalasban. Peldaul ennek segitsegevel mutatta meg Hastad 1996-ban, hogy a grafok maximalis klikkmeretenek becslesere addig talalt algoritmusok nem veletlenul annyira rossz hatasfokuak: ahogy az a cikkenek a cimeben is all, "Clique is Hard to Approximate within n^(1-epsilon)".
Egy korabbi eloadason a PCP tetel Dinur-fele bizonyitasat neztuk meg (helyesebben: annak egy-ket fontosabb mozzanatat), most az alkalmazason lesz a hangsuly. Mindezt a KLIKK probleman keresztul tervezem megmutatni, de igyekszem minel inkabb az altalanos modszereket ismertetni. Elokerulnek tehat interaktiv protokollok, linearitas teszteles es Raz parhuzamos ismetlesi tetele ("parallel repetition theorem"), majd legvegul a mostanaban igencsak eloterben levo Unique Games Conjecture-rol lenne szo - illetve az azzal kapcsolatos legujabb fejlemenyekrol. Varhatoan tobb alkalomra szetosztva.
Minden erdeklodot szeretettel varunk,
Peter