削減が正しいことを確認する

アリスは多項式時間で計算できる$ f: {0,1 } ^ * から {0,1 } ^ *
$までの関数を持っています。彼女は$ x in mathrm {SAT} iff f(x) in mathrm
{CLIQUE} $と主張する。アリスは集合$ {0,1 } ^ n $上の$ f $を計算する回路をボブに送る。ボブは$
mathbf {P} ^ { mathrm {SAT}} $(または$ mathbf {P}
$)のアルゴリズムです。彼は、長さ$ n $のすべての入力に対して、$ f $が確かに$ mathrm {SAT} $〜$
mathrm {CLIQUE} $の正しい削減であることを検証したいと考えています。
そのようなボブが存在する場合、それは多項式階層の崩壊を意味するのだろうか?

言い換えれば、 {0,1 } ^ n colon x in mathrm {SAT} iff C(x)
in mathrmにある$ {C text { {CLIQUE} } $ (ここで$ n $は$ C
$の入力ゲートの数です)。 $ Pi_2 ^ P $ -complete? $ mathbf {NP} $ –
ハード?クリークとSATは私が選んだ任意の$ mathbf {NP} $の完全な言語です。

ベストアンサー

これは$ Pi_2 ^ p $ -completeです。 SATからCLIQUEへの通常の削減をDとする。
wをCLIQUEの文字列とします。すべての$ y $に対して$ z $があるような$ x $の集合として表現される$ Pi_2 ^
p $言語$ L $を考えてみましょう。$ z $は$ A($、y、z) P ($ y $と$ z
$の多項式の長さの境界)のA $です。 $(x、y、z)$が$ A $にある$ z $が存在する場合、$ phi_ {x、y}
$を充足可能な式にします。

次のように$ C_x( phi)$を定義する:ある$ y $について$ phi = phi_ {x、y} $ならば$
C_x( phi)= w $とすると、$ C_x( phi)= D ( phi)$です。

$ C_x $がSATからCLIQUEに減少した場合にのみ、$ x $は$ L $に入ります。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です