Genomsnittligt argument

I beräkningskomplexitetsteori och kryptografi är medelvärdesargument ett standardargument för att bevisa teorem . Det tillåter oss vanligtvis att konvertera probabilistiska polynomtidsalgoritmer till olikformiga kretsar av polynomstorlek .

Exempel

Exempel: Om varje person gillar minst 1/3 av böckerna i ett bibliotek, så har biblioteket en bok som minst 1/3 av människorna gillar.

Bevis: Anta att det finns $N$ personer och $B$ böcker. Varje person gillar minst $B/3$ av böckerna. Låt folk lämna ett spår i boken de gillar. Då kommer det att finnas minst $M=(NB)/3$ märken. Genomsnittsargumentet hävdar att det finns en bok med minst $N/3$ markeringar. Antag, motsägelsefullt, att det inte finns någon sådan bok. Sedan har varje bok färre än $N/3$ markeringar. Men eftersom det finns $B$ -böcker kommer det totala antalet markeringar att vara färre än $(NB)/3$ , vilket motsäger det faktum att det finns minst $M$ märken. $\scriptstyle \blacksquare$

Formaliserad definition av medelvärdesargument

Låt X och Y vara mängder, låt p vara ett predikat på X × Y och låt f vara ett reellt tal i intervallet [0, 1]. Om för varje x i X och åtminstone f |Y| av elementen y i Y uppfyller p ( x , y ), då finns det ett y i Y så att det finns åtminstone f |X| element x i X som uppfyller p ( x , y ).

Det finns en annan definition, definierad med hjälp av terminologin för sannolikhetsteorin .

Låt $f$ vara någon funktion. Medelvärdesargumentet är följande påstående: om vi har en krets $C$ så att $C(x,y)=f(x)$ med sannolikhet vid minst $\rho$ , där $x$ väljs slumpmässigt och $y$ väljs oberoende av någon fördelning $Y$ över $\{ 0,1\}^{m}$ (som kanske inte ens går att sampla effektivt) så finns det en enda sträng $y_{0}\in \{0,1\}^{ m}$ så att $\Pr _{x}[C(x,y_{0})=f(x)]\geq \ rho$ .

Faktum är att för varje $y$ definiera $p_{y}$ att vara $\Pr _{x}[C( x,y)=f(x)]$ sedan

$\Pr _{x,y}[C(x,y)=f(x)]=E_ {y}[p_{y}]\,$

och sedan reduceras detta till påståendet att för varje slumpmässig variabel $Z$ , om $E[Z]\geq \rho$ så $\ Pr[Z\geq \rho ]>0$ (detta gäller eftersom $E[Z]$ är det viktade medelvärdet av $Z$ och tydligt om medelvärdet av vissa värden är minst $\rho$ då måste ett av värdena vara minst ${\displaystyle \rho } )$ .

Ansökan

Detta argument har stor användning i komplexitetsteori (t.ex. att bevisa ${\displaystyle {\mathsf {BPP}}\subsetneq {\mathsf {P/poly}}})$ och kryptografi (t.ex. bevisa att oskiljbar kryptering resulterar i semantisk säkerhet ). En uppsjö av sådana applikationer finns i Goldreichs böcker.