v kryptografie a teorie výpočtu, další bitový test[1] je test proti generátory pseudonáhodných čísel. Říkáme, že posloupnost bitů projde dalším testem bitů na jakékoli pozici
v pořadí, pokud existuje nějaký útočník, který zná
první bity (ale ne semeno) nemohou předvídat
s rozumnou výpočetní silou.
Přesné prohlášení
Nechat
být polynomem a
být souborem sad takových, že
obsahuje
-bit dlouhé sekvence. Navíc nechte
být rozdělení pravděpodobnosti strun dovnitř
.
Nyní definujeme další bitový test dvěma různými způsoby.
Booleovská formulace obvodu
Predikční kolekce[2]
je sbírka booleovské obvody, takže každý obvod
má méně než
brány a přesně
vstupy. Nechat
je pravděpodobnost, že na vstupu
první kousky
, řetězec náhodně vybraný v
s pravděpodobností
, obvod správně předpovídá
, tj. :
![{ displaystyle p_ {k, i} ^ {C} = { mathcal {P}} vlevo [C_ {k} (s_ {1} ldots s_ {i}) = s_ {i + 1} vpravo | s in S_ {k} { text {s pravděpodobností}} mu _ {k} (y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8121de2c7bf08636284eda500f8d696acd0003b9)
Nyní to říkáme
projde dalším bitovým testem, pokud jde o jakoukoli predikční kolekci
, jakýkoli polynom
:

Pravděpodobnostní Turingovy stroje
Můžeme také definovat další bitový test z hlediska pravděpodobnostní Turingovy stroje, ačkoli tato definice je poněkud silnější (viz Adlemanova věta ). Nechat
být pravděpodobným Turingovým strojem pracujícím v polynomiálním čase. Nechat
je pravděpodobnost, že
předpovídá
st bit správně, tj.
![{ displaystyle p_ {k, i} ^ { mathcal {M}} = { mathcal {P}} [M (s_ {1} ldots s_ {i}) = s_ {i + 1} | s in S_ {k} { text {s pravděpodobností}} mu _ {k} (y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7766a3f48e5a6d071679f8541dc9fccbc6a94df)
Říkáme tu sbírku
projde dalším bitovým testem, pokud pro všechny polynomy
, pro všechny, ale konečně mnoho
, pro všechny
:

Úplnost testu Yao
Další bitový test je konkrétním případem Yaův test pro náhodné sekvence a jejich předání je tedy a nutná podmínka pro průchod Yaův test. Bylo však také prokázáno, že dostatečný stav podle Yao.[1]
Nyní to dokazujeme u pravděpodobnostního Turingova stroje Adleman již v roce nahradil randomizaci nerovnoměrností jeho věta. Případ booleovských obvodů nelze z tohoto případu odvodit (protože zahrnuje rozhodování o potenciálně nerozhodnutelných problémech), ale důkaz Adlemanovy věty lze snadno přizpůsobit případu nejednotných rodin booleovských obvodů.
Nechat
být rozlišovacím znakem pravděpodobnostní verze testu Yao, tj. pravděpodobnostní Turingův stroj běžící v polynomiálním čase, takže existuje polynom
takové, že pro nekonečně mnoho 

Nechat
. My máme:
a
. Pak si toho všimneme
. Proto alespoň jeden z
by neměla být menší než
.
Dále uvažujeme rozdělení pravděpodobnosti
a
na
. Rozdělení
je rozdělení pravděpodobnosti výběru
první bity dovnitř
s pravděpodobností danou
a
zbývající bity náhodně rovnoměrně. Máme tedy:


Máme tedy
(ukazuje to jednoduchý trik kalkulu), tedy distribuce
a
lze rozlišit podle
. Bez ztráty všeobecnosti to můžeme předpokládat
, s
polynom.
To nám dává možnou konstrukci Turingova stroje řešícího test dalšího bitu: po obdržení
první bity sekvence,
vyplní tento vstup hádáním bitů
a pak
náhodné bity, vybrané s jednotnou pravděpodobností. Pak to běží
a výstupy
pokud je výsledek
, a
jiný.
Reference