Průměrný argument - Averaging argument
v teorie výpočetní složitosti a kryptografie, průměrný argument je standardní argument pro dokazování vět. Obvykle nám to umožňuje konvertovat pravděpodobnostní polynomiální čas algoritmy do nejednotné obvody polynomické velikosti.
Příklad
Příklad: Pokud se každému člověku líbí alespoň 1/3 knih v knihovně, pak má knihovna knihu, která se líbí alespoň 1/3 lidem.
Důkaz: Předpokládejme, že existují lidé a knihy B. Každá osoba má alespoň ráda knih. Umožněte lidem zanechat stopu na knize, která se jim líbí. Pak tam bude přinejmenším známky. Argument průměrování tvrdí, že existuje alespoň kniha s značky na něm. Předpokládejme, v rozporu, že taková kniha neexistuje. Pak má každá kniha méně než známky. Protože však existují knih, celkový počet známek bude menší než , což je v rozporu se skutečností, že existují alespoň známky.
Formalizovaná definice průměrného argumentu
Nechat X a Y buď soupravy, ať str být predikát na X × Y a nechte F být reálné číslo v intervalu [0, 1]. Pokud pro každého X v X a alespoň f | Y | prvků y v Y uspokojit str(X, y), pak existuje a y v Y takové, že existují alespoň f | X | elementy X v X které uspokojují str(X, y).
Existuje další definice definovaná pomocí terminologie teorie pravděpodobnosti.[1]
Nechat být nějakou funkcí. Argumentem průměrování je následující tvrzení: pokud máme obvod takhle alespoň s pravděpodobností , kde je vybrán náhodně a je vybrán nezávisle na některých rozdělení přes (což ani nemusí být efektivně vzorkovatelné ) pak existuje a singl tětiva takhle .
Opravdu pro každého definovat být pak
a pak se to redukuje na tvrzení, že pro každou náhodnou proměnnou , pokud pak (to platí od té doby je vážený průměr a jasně, pokud je průměr některých hodnot alespoň pak jedna z hodnot musí být alespoň ).
aplikace
Tento argument má široké použití v teorie složitosti (např. dokazování ) a kryptografie (např. prokazování toho nerozeznatelné šifrování výsledky v sémantická bezpečnost ). Nepřeberné množství takových aplikací lze nalézt v Goldreich knihy.[2][3][4]
Reference
- ^ Barak, Boaz (Březen 2006). „Poznámka k průměrování a hybridním argumentům a predikci vs. rozlišení“ (PDF). COS522. Univerzita Princeton.
- ^ Oded Goldreich, Základy kryptografie, svazek 1: Základní nástroje, Cambridge University Press, 2001, ISBN 0-521-79172-3
- ^ Oded Goldreich, Základy kryptografie, svazek 2: Základní aplikace, Cambridge University Press, 2004, ISBN 0-521-83084-2
- ^ Oded Goldreich, Výpočetní složitost: koncepční perspektiva, Cambridge University Press, 2008, ISBN 0-521-88473-X