0/1整数プログラミングを解くことでACCのSYM回路を解く

私はこのSTOC 2014論文の定理1.4の証明を参照しています。 https://arxiv.org/abs/1401.2444
をご覧ください。特に私の質問は、9ページの8行目から始まる議論です。著者は次のように述べています。

“Following the strategy of Theorem 1.2 (and the author’s ACC SAT
algorithm https://www.cs.cmu.edu/~ryanw/acc-lbs.pdf),
the satisfiability question of (a $AC^0[2]circ SYM$) C with $n$
inputs and size $poly(s)$ can be efficiently converted into a
problem of evaluating a larger $AC^0[2]circ SYM$ circuit C’ where
C’ has $(n-k)$ inputs, $2^ktimes poly(s,M)$ size and $k <
frac{n}{2}$ is a parameter and the $AC^0$ part has depth $6$. More
precisely C’ is an OR of $2^k$ copies of the depth $5$ circuit $C$
and each copy has its first $k$ inputs assigned to a distinct
string from ${0,1}^k$.”

ここでC
‘が回路Cを与えられてどのように定義されるかを考えると、回路C’はCが充足可能である場合にのみ充足可能であることは明らかである。

なぜなら、$ C $が深さ$ 5 $回路である理由は、ページの上部にある$ 9 $から、その$ AND
circまたはcircと circ { circ XOR circおよび circまたは circ SYM
$になります。 $ C $の$ AC ^ 0 [2] $部分は深さ$ 6
$でなければならず、段落の最初の部分と一致します。私は引用された段落のこの “深さ5″部分がタイプミスだと思います!…)

この議論をするには、この論文の定理1.2($ ACC circ THR
$回路を評価するための高速アルゴリズム)と引用した大きな画期的な論文のような、より深い定理が必要な場合はどこですか?
(この証拠の後の段階では、これらの2つの大きな結果がどちらかに言及されているのを見ています)。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

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