すべてのブール関数を$(MOD_2-MOD_3)$回路で計算できることの証明

I was reading “Some properties of MOD m circuits computing
simple functions” (Amano & Maruoka, 2003) where the authors prove
that every Boolean function can be computed by depth $2$ by
$(MOD_2-MOD_3)$ circuit. They claim what follows:

$ n $の$ OR $関数は、   変数、すなわち、$ vee_ {i = 1} ^ n x_i $
  、することができます
  深度2の$(MOD_3-MOD_2)$回路で計算されます。

私は上記の部分に同意し、私は$ n $ -ary $ OR $の建設を示すことができます。この事実に基づいて、

これは、$ n $のすべての論理和   すなわち、$ vee_ {i = 1} ^ n l_i $
  ここで$ l_i in {x_i、 overline {x_i} } $
  、   深さ2の$(MOD_3-MOD_2)$回路でも計算できます。

私も受け入れます。その後、彼らは主な証拠の根拠を設定した。

$ f $を$ n $の任意のブール関数とする   変数。 CNFの式が   $ f
$、各節には正確に$ n $   リテラル。一般性を失うことなく、私たちは   数式に$ m
equiv 1( mod 3)$ clausesがあると仮定できます。

ここまでは順調ですね。しかし、私が失った部分が来る:

$ f $の値が0の場合、$ m-1 equiv 0( mod 3)$   $ f $の節は$ 1
$をとり、$ f $の値が   $ 1 $であれば、$ m equiv 0( mod 3)$句のすべてが$
1 $という値をとります。したがって、入力がすべて$(MOD_3-MOD_2)$である$ MOD_3 $ゲート
  回路は、CNF式の各節を計算し、func-   $ f $

誰も私に理由を説明してもらえますか?

$ f $の値が0の場合、$ m-1 equiv 0( mod 3)$   $ f
$の値は$ 1 $となります。

本当ですか? $ m $句を持つCNFが$ 0 $に評価され、$ m-2 $句が真であることは可能ですか?または$ m-3
$または$ m-113 $。たとえば、私のCNFが$ n $の大きな$ AND
$変数の場合はどうでしょうか?それから、これは成り立ちません。どんな数の条項も「死んでいる」かもしれません…

(これはすべての証拠ではないことに注意してください。この大きな回路をより小さな回路に変換する方法を示す必要があります)。

ベストアンサー

重要な観察は、$ f $がCNFによって表されるのではなく、すべての節が個の変数を持つ$ n
$リテラルを持つCNFであることです。ここで$ n $は変数の数です。

このようなCNFが存在することは容易に分かります。実際、$ S $を$ neg f $の解の集合とする。 S $の各解$ s
は$ n $リテラルの連合として見ることができます。たとえば、$ s = {x = 0、y = 1、z = 0 } $は$
neg x wedge y wedge neg z $と見なすことができます。したがって、$ neg f =
bigvee_ {s in S} s $、次に$ f = bigwedge_ {s in S} neg s
$はCNF式です。

これはCNFの節が、$ F $と呼ぶので、変数の割り当てと一対一に対応しているので、これは重要です。各節$ neg s $
of $ F $には、$ s $、句を満たさない唯一の割り当て。例えば、$ neg s = x vee neg y
vee z $を満たさない唯一の方法は$ s = {x = 0、y = 1、z = 0 }
$です。したがって、割当てを考えると、$ F $の1つの節は満たされない。

今、まだ何か説明があります。著者らは、$ m equiv 1 mod 3 $
wlogと仮定できると主張する。人為的に条項の数を増やすことはできず、以前の財産が残っているので、それは完全に真実ではありません。しかし、議論のために、常に
$ 1 $に評価する$ x vee neg x $のような些細な節を追加すれば十分です。

返信を残す

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