ランダムな自己還元性

ランダム自己還元性( RSR ) とは、平均的なケースに適したアルゴリズムは、最悪のケースにも適したアルゴリズムであるという規則です。RSR は、インスタンスの大部分を解決することで、問題のすべてのインスタンスを解決する能力です。

関数 fについて、任意のインスタンスx を評価することが、 1 つ以上のランダムなインスタンスy _iに対するfの評価に多項式時間で簡約できる場合、それは自己簡約可能です (これは、非適応型一様自己簡約とも呼ばれます)。ランダム自己簡約では、 fのドメイン内の任意の最悪ケースのインスタンスx が、インスタンスのランダムなセットy ₁、...、y _kにマッピングされます。これは、マッピングからのコイントスシーケンスx 、およびf ( y ₁ )、...、f ( y _k ) が与えられた場合、 f ( x ) を多項式時間で計算できるようにするために行われます。したがって、 y _i上の誘導分布に関して平均を取ると、fの平均ケースの複雑度は、 fの最悪ケースのランダム化された複雑度と同じになります (多項式因数内)  。

注目すべき特別なケースの 1 つは、各ランダム インスタンスy _{i が}、長さが | x | であるfのドメイン内の要素のセット全体に均一に分布している場合です。この場合、 f は平均的にも最悪の場合と同じくらい困難です。このアプローチには、2 つの重要な制限があります。まず、y ₁、...、y _kの生成は非適応的に実行されます。つまり、y _{2 は}f ( y ₁ ) がわかる前に選択されます。次に、ポイントy ₁、...、y _{k が}均一に分布している必要はありません。

データに何らかのプライバシーを必要とする問題 (通常は暗号化の問題) では、ランダム化を使用してプライバシーを確​​保できます。実際、唯一証明可能な安全性を持つ暗号化システム (ワンタイム パッド) のセキュリティは、システムに提供されるキー データの ランダム性に完全に依存しています。

暗号学の分野では、特定の数論的関数がランダムに自己還元可能であるという事実を利用しています。これには、確率的暗号化や暗号的に強力な疑似乱数生成が含まれます。また、インスタンス隠蔽スキーム（弱いプライベートデバイスがデータを公開せずに強力なパブリックデバイスを使用するスキーム）は、ランダムな自己還元によって簡単に例示できます。

離散対数問題、二次剰余問題、RSA反転問題、行列のパーマネントを計算する問題は、それぞれランダムな自己簡約問題です。

定理:サイズ | G | の巡回群Gが与えられます。決定論的多項式時間アルゴリズムAが、すべての入力の1/poly( n ) 分数の離散対数を計算する場合 (ここで、 n = log | G | は入力サイズ)、すべての入力の離散対数に対するランダム化多項式時間アルゴリズムが存在します。

巡回群 G = { g i | 0 ≤ i < | G | } の生成元 g^とx ∈ Gが与えられたとき、基数gに対するxの離散対数は整数k (0 ≤ k < | G |) で、x = g ^kである。B が{0,...,| G | − 1}上に一様に分布しているとすると、 xg ^B = g ^{k + B}もG上に一様に分布する。したがって、xg ^{B は}xに依存せず、その対数は確率 1/poly( n ) で多項式時間で計算できる。すると、 log _g x ≡ log _g xg ^B - B (mod | G |) となり、離散対数は自己約分可能である。

行列のパーマネントの定義が与えられれば、任意のn行n列の行列MのPERM ( M )は、 Mの要素に対するn次多変数多項式であることは明らかです。行列のパーマネントを計算することは難しい計算タスクです。PERMは#P 完全であることが示されています(証明)。さらに、ほとんどの行列についてPERM ( M )を計算できるということは、すべての行列についてPERM ( M )を計算するランダム プログラムが存在することを意味します。これは、 PERM がランダム自己約可能であることを示しています。以下の説明では、行列の要素が何らかの素数pの有限体F _pから抽出され、すべての演算がその体で実行される場合を検討します。

X をF _pからの要素を持つランダムなn行n列の行列とします。任意の行列M + kXのすべての要素はkの線形関数であるため、これらの線形関数をPERM ( M ) を計算するn 次多変数多項式と合成すると、 k上の別のn次多項式が得られ、これをp ( k )と呼びます。明らかに、p (0) はMのパーマネントに等しくなります。

F _pからの要素を持つn行n列の行列のほとんど（具体的には、 1 − 1/(3 n ) 個）についてPERM ( A )の正しい値を計算するプログラムがあるとします。すると、約 3 分の 2 の確率で、k = 1,2,..., n + 1についてPERM ( M + kX ) を計算できます。これらのn + 1 個の値がわかれば、補間を使用してp ( k )の係数を解くことができます（p ( k ) の次数はnであることに注意してください）。 p ( k ) が正確にわかれば、 PERM ( M )に等しいp (0)を評価します。

そうすると、1/3 の確率で間違えるリスクがありますが、複数のランダムなXを選択し、上記の手順を何度も繰り返し、多数決で選ばれた答えだけを答えとして提供することで、エラー率を非常に低く抑えることができます。

• NP完全問題が非適応ランダム自己還元可能であれば、多項式階層はΣ ₃に縮小されます。
• CoNP困難な問題がO (log n / n )でランダム自己還元可能である場合、Σ ₂ = Π ₂となります。

• M. Abadi、J. Feigenbaum、J. Kilian、「オラクルからの情報の隠蔽について」、J. Comput. Syst. Sci.、1989
• S. アローラ『PCP 定理の周辺』、1996 年
• J. ファイゲンバウム、L. フォートナウ、「完全集合のランダム自己還元性について」、1991 年