垂直方向および水平方向の制約下でのマトリックスの色付け

私は、次のNP完全な問題の正しい名前を探しています。同様の見た目のバリエーションを持つ問題を指し示す答えもありがたいです。

入力は

  • $ Sigma $ = $ Sigma | = n ^ {O(1)} $の色の集合。
  • 各エントリ$ M_ {ij} $が$ Sigma $
  • のサブセットである$ nxn $の正方行列$ M $

  • [n-1] $内の$ i inと[n-1] $内の各$ j に対して、水平制約の$ H_ {ij} subseteq
    Sigma times Sigma $を設定します。
  • [n-1] $および各$ j in [n] $に対して、垂直制約の$ V_ {ij} subseteq Sigma
    times Sigma $が設定されます。

問題の解は、各エントリ$ N_ {ij} $が$ M_ {ij} $に属する$ n times n $行列$ N
$であり、それぞれが水平方向に連続する$ {N_ {ij}、N_ {i (i + 1)})$は$ H_ {ij}
$に属し、垂直方向に連続する各エントリ$(N_ {ij}、N_ {(i + 1)j})$は$ V_ {ij} $に属する。

ベストアンサー

A1) The problem remains NP-complete even for
fixed $|Sigma|=3$

平面1-3-SATからの減少は以下の通りである。 $ Sigma = {0,1,2 } $とする

  • 真偽値を「キャリー」するために、水平/垂直セルの$ M_ {ij} = {0,1 } $
    ペアのシーケンスを「ワイヤ」ガジェットとして使用します($ 0 = true $、$ 1,2 =偽$)の変数($
    true leftrightarrow偽$の切り替えを禁止するワイヤの水平および垂直ルール)
  • ワイヤの始まりは「変数の割り当て」として機能します
  • 水平と垂直の規則が回路に沿って$ 012 ; 012 ….
    $のシーケンスを強制する円形パターンを使って句をシミュレートします
  • 各節には3本の入力線があります。ワイヤは3つの別個の場所モジュロ3
    で回路に「触れる」ように配置されている。このようにして、3つのワイヤのうちの1つだけが真の値を持つことができます。

次の図は、自明のものでなければなりません。

enter image description here

「ローカル」水平/垂直ルールの代わりに、「グローバル」ルール(すべてのセルに共通するルールのセット)を使用する場合は、ワイヤを「分離する」ために別の「空白」カラーを追加する必要があります。まだ保持しています。

$ | Sigmaを使って| = 2
$問題は多項式時間解法です(各セルはバイナリ変数で表され、ルールは2-SAT式で表現できます)。

A2) The game is also very similar to a
“relaxed” version of the game Binary
Puzzle
: a puzzle game played on a $n times n$ grid. Intially
some of the cells contain a zero or a one; the aim of the game is
to fill the empty cells according to the following rules:

  1. 各セルには0または1が含まれていなければならず、2つ以下の類似した数字は互いに隣り合っていても許されていません。
  2. 各行と各列には、同じ数のゼロと1を含める必要があります。
  3. 各行はユニークで、各列は一意です。

8色のセットを使用すると、バイナリパズルのルール#1(ルール#2と#3がなくてもNPCです)をシミュレートできます。これは削減のための簡単なアイデアです。

8つの色のそれぞれに3ビット$ b_0b_1b_2 $があります。

  • ビット0 $ b_0 $は、バイナリパズルグリッドの$ 0 $または$ 1 $を表します。
  • 左のセルの色が同じ場合にのみ、ビット1 $ b_1 $は$ 1です。
  • 上のセルの色が同じ場合にのみ、ビット2 $ b_2 $は$ 1 $です。

バイナリパズルの最初のボードのセル$ i、j $が空の場合、$ M_ {ij} = Sigma $

バイナリパズルの最初のボードのセル$ i、j $が強制的な$ 1 $ならば、$ M_ {ij} = {1 ** }
$(100,101,110,111)

バイナリパズルの最初のボードのセル$ i、j $が強制的な$ 0 $ならば、$ M_ {ij} = {0 ** }
$(000,001,010,011)

水平ルールは次のとおりです。

00* -> 01*  : allow another 0 on the right only if the previous was 1
0** -> 1**  : always allow a 0->1 transition
10* -> 11*  : allow another 1 on the right only if the previous was 0
1** -> 0**  : always allow a 1->0 transition

垂直方向のルールは次のとおりです。

0*0 -> 0*1  : allow another 0 below only if the above one was 1
0** -> 1**  : always allow a 0->1 transition
1*0 -> 1*1  : allow another 1 below only if the above one was 0
1** -> 0**  : always allow a 1->0 transition

バイナリパズルのNP完全性の証明をご覧いただけます。私のブログ(すぐにまたは後で私はどこかにそれを提出する時間を見つけるでしょう)。

A3) Furthermore if you add the constraint
that each color can be used only once
, then the problem is
still NPC even on $n times 1$ grids with only horizontal
constraints.

この削減は3-PARTITIONからです。これは強力なNPCです:集合$ X = {x_1、…、x_ {3q} }
$と目標合計$ B =( sum x_i)/ 3 $; $ x_i $ごとに(新しい)色$ c ^ i_1、…、c ^ i_i
$を使用します。長さ$ Bq + q + 1 $のグリッド$ G $から、次の許容色のセットを使用して開始します。

$ S E ^ B T_1 E ^ B T … E ^ B T_q $

どこで

  • $ S $(集合$ M_1 $)は開始色$ {c_S } $
  • を表します。

  • $ T_i $は、$ q $特殊色を含む中断ブロックを表します。$ {{c_ {Ti} } $
  • $ E ^ B $は、$ Sigma setminus {c_S、c_ {Ti} } $
  • から任意の色を含むことができる$ B $ “ブロック”

水平方向の制約は次のとおりです。

    $ S $から始まり、$ c ^ i $ のカラーシーケンスを使うことを可能にする、$ i = 1 … n $の$(S、c
    ^ i_1) $ j = 1 … i-1 $:のための$(c ^ i_j、c ^ i_ {j + 1})$は、各$ c ^ i
    $(一度開始された)の完全なカラーシーケンス

  • $ i neq j $の$(c ^ i_i、c ^
    j_1)$これは、前回終了した別のカラーシーケンスを開始することができます。
  • $ i = 1 … n、j = 1.q-1 $の場合、$(c ^ i_i、c_
    {Tj})$:カラーシーケンスをブレー​​クブロックに「並べる」 “単項”の合計は$ B $に等しい)
  • $ i = 1 … n、j = 1..q-1 $の場合、$(c_ {Tj}、c ^
    i_1、$):ブレークブロックの後に別のカラーシーケンスを許可する$ T_j $ < >

元の3-PARTITION問題に解がある場合に限り、$ n times 1 $ grid $ G
$は適切に着色されます。

これは例です:3-PARTITIONインスタンスを指定すると:

$ A = {3,3,2,2,2,2 } ; (B = 7、q = 2)$

図のように、$ 2B + 2 $の別個の色を使用し、$ 2B + 2 + 1 = 17 times 1
$グリッドで着色ゲームインスタンスを構築することができます。

enter image description here

返信を残す

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