ヴァリアント・ヴァジラニ定理

ヴァリアント・ヴァジラニ定理は、計算複雑性理論における定理で、一義的 SATに対する多項式時間アルゴリズムが存在する場合、NP  =  RPとなることを述べています。これは、レスリー・ヴァリアントとビジェイ・ヴァジラニが1986 年に発表した「NP は一意の解を検出するのと同じくらい簡単」という論文で証明されました。 ^[1]

Valiant-Vazirani の定理は、入力インスタンスが最大で 1 つの満足できる割り当てを持つことが約束されている場合でも、 NP 完全であるブール値の充足可能性問題は計算上困難な問題のままであることを意味します。

曖昧さのない SAT は、最大で 1 つの満足する割り当てを持つブール式が満足できないか、または 1 つの満足する割り当てだけを持つかを決定する約束問題です。前者の場合、曖昧さのない SAT のアルゴリズムは式を拒否し、後者の場合、式を受け入れます。式に複数の満足する割り当てがある場合、アルゴリズムの動作に条件はありません。約束問題である曖昧さのない SAT は、最大で 1 つの受け入れ計算パスを持つ非決定性チューリング マシンによって決定できるため、複雑性クラスUPの約束バージョンに属します(クラス UP 自体は言語に対してのみ定義されています)。

ヴァリアント・ヴァジラニの定理の証明は、n変数の式Fが与えられたときに、次のような 式のシーケンスG ₀、...、G _{n を出力する確率的還元で構成されています。}

• 任意のG _iの満足する割り当てはすべてFも満たします。したがって、Fが満足できない場合、すべてのG _i（i ≤ n ）は満足できません。
• Fが満足可能な場合、少なくとも 1/4 の確率で、何らかのG _{i に}一意の満足する割り当てが存在します。

この簡約の考え方は、式Fの解空間を内のn個のランダムな線形超平面と順次交差させることです。 ${\displaystyle \mathbb {F} _{2}^{n}}$

結果として（NP = RP の議論には必要ありませんが、独立した関心事です）、G _iの 1 つをランダムに選択すると、少なくとも Ω(1/ n )の確率で成功する、SAT から Unambiguous-SAT への片側誤差を伴うランダムな縮約が得られます。つまり、Fが満たされない場合、出力式は常に満たされず、Fが満たされる場合、出力式には確率 Ω(1/ n )で一意の満足割り当てがあります。

ここで、Unambiguous-SAT が多項式時間アルゴリズムAによって解決可能であると仮定すると、各i ≤ nについてG _iに対してA を実行することで、SAT のRPアルゴリズムが得られます。Fが満たされない場合、A は満たされないすべてのG _{i を}拒否しますが、Fが満たされる場合、A は少なくとも 1/4 の確率でいくつかのG _{i を}受け入れます。(この削減を数回繰り返すことで、受け入れ確率を向上させることができます。)

より一般的には、この議論はNPがRP ^promiseUPに含まれていることを無条件に示します。

代替の証明は、Mulmuley、Vazirani、Vazirani による孤立性の補題に基づいています。彼らはより一般的な設定を考慮しており、ここでの設定に適用すると孤立性の確率は のみになります。 ${\displaystyle \Omega (1/n^{8})}$