SATからバイナリ行列サブセット問題への削減

この質問の@Denisによる回答を理解しようとしていますでは、SATからバイナリ行列の列サブセットの選択問題に還元する方法を示しました。私が新しい質問を投稿しなければならないのは、前にcstheory.stackexchangeのアカウントがないからです。私は彼に直接尋ねることができません。

コメントの彼の方法についての彼の説明では、彼は行列の構築によって、[1、m] $のすべての$ i に対して$ x_i、
neg x_i $列のうちの1つだけを選択するように強制され、すなわち、CNFへの割り当てを強制する(私は、$ 2m $列の中から$
m $を選択しなければならないという以前の主張のために信じている)。私はなぜこれが当てはまるのかを理解するのに苦労しています。$
m_$以上の列を選択するか、$ x_i $と$ neg x_i $を表す列を両方選択すると、間違いはありません。

ベストアンサー

元の問題は、この$ k $の解があるかどうかにかかわらず、与えられた$ k $を求めるので、$ k = m
$をインスタンス化することができます。つまり、$ m $の列を選択する必要があります。 次に、$ x_i $と$ neg x_i
$の両方を選択すると、行番号$ j $にゼロだけが残るように$ j $が存在するため、この選択はうまくいくことはありません。

返信を残す

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