次のビットのテスト

暗号理論および計算理論において、次ビットテスト^{[ 1 ]}は擬似乱数発生器に対するテストである。ビット列が任意の位置で次ビットテストに合格するとは、${\displaystyle i}$シーケンス内で、${\displaystyle i}$最初のビット（シードではない）は予測できません${\displaystyle (i+1)}$適切な計算能力で処理します。

させて${\displaystyle P}$多項式であり、${\displaystyle S=\{S_{k}\}}$集合の集合であって、${\displaystyle S_{k}}$を含む${\displaystyle P(k)}$ビット長のシーケンス。さらに、${\displaystyle \mu _{k}}$文字列の確率分布を${\displaystyle S_{k}}$。

次に、次ビット判定を2つの異なる方法で定義します。

次のビットのテストは、ランダムなシーケンスに対するヤオのテストの特殊なケースであり、したがって、このテストに合格することは、ヤオのテストに合格するための必要条件である。しかし、ヤオによって十分条件であることも示されている。^{[ 1 ]}

アドレマンは既に自身の定理においてランダム化を非一様性に置き換える作業を終えているため、ここでは確率的チューリングマシンの場合について証明する。ブール回路の場合は（潜在的に決定不能な問題の決定を伴うため）このケースから導出することはできないが、アドレマンの定理の証明は非一様ブール回路ファミリーの場合に容易に適用できる。

させて$\displaystyle {\mathcal {M}}}$ヤオのテストの確率的バージョンの識別器、つまり多項式時間で動作する確率的チューリングマシンであり、多項式が存在する。${\displaystyle Q}$無限に多くの${\displaystyle k}$

${\displaystyle |p_{k,S}^{\mathcal {M}}-p_{k,U}^{\mathcal {M}}|\geq {\frac {1}{Q(k)}}}$

させて${\displaystyle R_{k,i}=\{s_{1}\ldots s_{i}u_{i+1}\ldots u_{P(k)}|s\in S_{k},u\in \{0,1\}^{P(k)}\}}$。 我々は持っています：${\displaystyle R_{k,0}=\{0,1\}^{P(k)}}$そして${\displaystyle R_{k,P(k)}=S_{k}}$すると、次のことに気づきます。${\displaystyle \sum _{i=0}^{P(k)}|p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|\geq |p_{k,R_{k,P(k)}}^{\mathcal {M}}-p_{k,R_{k,0}}^{\mathcal {M}}|=|p_{k,S}^{\mathcal {M}}-p_{k,U}^{\mathcal {M}}|\geq {\frac {1}{Q(k)}}}$したがって、少なくとも1つは${\displaystyle |p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|}$より小さくあってはならない${\displaystyle {\frac {1}{Q(k)P(k)}}}$。

次に、確率分布について考察します。${\displaystyle \mu _{k,i}}$そして${\displaystyle {\overline {\mu _{k,i}}}}$の上${\displaystyle R_{k,i}}$。 分布${\displaystyle \mu _{k,i}}$選択する確率分布は${\displaystyle i}$最初の部分${\displaystyle S_{k}}$確率は次のように与えられる${\displaystyle \mu _{k}}$、そして${\displaystyle P(k)-i}$残りのビットは一様にランダムに配置される。したがって、次のようになる。

したがって、${\displaystyle \mu _{k,i}={\frac {1}{2}}(\mu _{k,i+1}+{\overline {\mu _{k,i+1}}})}$（簡単な微積分トリックでこれがわかる）、したがって分布${\displaystyle \mu _{k,i+1}}$そして${\displaystyle {\overline {\mu _{k,i+1}}}}$区別できる$\displaystyle {\mathcal {M}}}$一般性を失うことなく、次のように仮定できる。${\displaystyle p_{\mu _{k,i+1}}^{\mathcal {M}}-p_{\overline {\mu _{k,i+1}}}^{\mathcal {M}}\geq {\frac {1}{2}}+{\frac {1}{R(k)}}}$、 と${\displaystyle R}$多項式。

これにより、次のビットテストを解くチューリングマシンの構成例が得られます。${\displaystyle i}$シーケンスの最初の部分、$\displaystyle {\mathcal {N}}}$この入力にビットの推測値をパディングします${\displaystyle l}$その後${\displaystyle P(k)-i-1}$一様確率で選択されたランダムなビット。そして、$\displaystyle {\mathcal {M}}}$出力${\displaystyle l}$結果が${\displaystyle 1}$、 そして${\displaystyle 1-l}$それ以外。