定期的な言葉で単語を達成するように文字をスケジュールすることができるかどうかをテストする

アルファベット$ Sigma $に標準言語 $ L $を修正しました。 $ L
$のレタースケジューリングと呼ばれる問題に続きます。非公式には、入力は私に$ n
$の文字と各文字の間隔(つまり、最小値と最大値)を与えます。私の目標は、2文字が同じ位置にマッピングされないように各文字をその間隔に配置することです$
n $の結果となる単語が$ L $にあることを確認します。正式には:

  • 入力:$ n $ triple $(a_i、l_i、r_i)$ $ a_i in Sigma $および$ 1
    leq l_i leq r_i leq n $は整数です。
  • 出力:$ l_i leq f(i) leq r_i $となるように$ f: {1、 ldots、n } から
    {1、 ldots、n すべての$ i $と$ a_ {f ^ { – 1}(1)} cdots a_ {f ^ { –
    1}(n)}

Obviously this problem is in NP, by guessing a bijection $f$ and
checking membership to $L$ in PTIME. My question: Is there
a regular language $L$ such that the letter scheduling problem for
$L$ is NP-hard?

いくつかの最初の観察:

  • 同様の問題がスケジューリングで研究されているように見えます。開始日と終了日を尊重しながら、1台のマシンでユニット単価のタスクをスケジューリングするという問題があります。しかし、この後者の問題は明らかに貪欲なアプローチのPTIMEであり、タスクがラベル付けされている場合のスケジューリング文献には何も表示されておらず、目標とする通常の言語で単語を達成したいと考えています。
  • この問題を見るもう1つの方法は、最大の2つの場合の特別なケースです(文字と位置の間で)一致する問題を解決できますが、$
    L $に落ちなければならないという制約を表現するのは難しいです。
  • $ L $が固定語$ u $(例えば$(ab)^ * $)の形式$ u ^ * $の言語である特定の場合、$ L
    $の文字スケジューリングの問題簡単な貪欲なアルゴリズムでPTIMEになります。単語を左から右に構築し、$ L
    $に対して相対的であり、最小時間$ r_i $を持つ利用可能な文字の各位置に1つ入れます。
    (正しい文字列がない場合は失敗します。)しかし、これは任意の正規言語$ L
    $には一般化されません。そのような言語では、使用する文字種を選択できるかもしれないからです。
  • ダイナミックアルゴリズムはうまくいくはずですが、実際はそれほど単純ではありません。あなたがこれまでに取った文字セットを暗記する必要があるようです。実際に、左から右に単語を構築するとき、$
    i
    $の位置に到達すると、あなたの状態はあなたがこれまでに消費した文字に依存します。指数関数的に多くの状態が存在するため、集合全体を覚えることはできません。しかし、あなたが使ったコピーを知るために、あなたがそれらを消費したときに覚えておく必要があるように見えるので、それを「要約」することは簡単ではありません(例えば、各レターのコピー数はどのくらい使われますか?より多くの手紙が利用可能であった)。
    $(ab | ba)^ * $のような言語であっても、$ abを取ることを選択する必要があり、後で必要となる文字に応じて$
    baを取ることを選択する必要があるときには、手紙が利用可能になったとき。
  • しかし、通常の$ L
    $は固定されており、多くの情報を覚えることができないので、私はNP困難な問題を見つけるのに苦労しています。
ベストアンサー

問題は$ L = A ^ * $のNP-hardです。$ A $は次の単語を含む有限の言語です:

  • $ x111 $、$ x000 $、
  • $ y100 $、$ y010 $、$ y001 $、
  • $ 00c11 $、$ 01c10 $、$ 10c01 $、および$ 11c00 $

この減少は、NP-hard(「a href =
“https://link.springer.com/article/10.1007/s00454-017-9884-9” rel =
“noreferrer” “>
https://link.springer.com/article/10.1007/s00454-017-9884-9
)。この問題では、すべての頂点に “$ {1 } $”または “$ {0,3 }
$”のラベルが付けられた3つの正規の無向グラフが与えられます。目標は、すべての頂点の外れ値がその頂点にラベルを付けるように、グラフの端を向けることです。

この削減は、Graph
Orientationインスタンスを入力として取り、トリプルのリストを出力として生成する必要があります。この削減では、出力するトリプルは常に一定の制約を満たします。これらの制約を以下に示します。これらの制約を満たす場合にのみ、トリプルのリストを有効と見なします。

  • The characters $x$, $y$, and $c$ are only given intervals
    containing exactly one index. In other words, whenever these
    characters are placed, they are placed in specific locations.
  • For every triple $(i, l, r)$ present in the instance with $i
    in {0,1}$, the triple $(1-i, l, r)$ is also present.
  • If $(alpha, l, r)$ and $(alpha’,l’,r’)$ are both triples
    present in the instance then either $l < l’ le r’ < r$, or
    $l’ < l le r < r’$, or ${alpha,alpha’} = {0,1}$ with
    $l = l’ < r = r’$.
  • If $(alpha, l, r)$ is a triple then the number of triples
    $(alpha’, l’, r’)$ with $l le l’ le r’ le r$ is exactly
    $r-l+1$.

このポストの最後に証明されている次の補題に注意してください。

補題:トリプルの有効なリストの場合、$ x $、$ y $、$ c
$の文字は、トリプルによって示された通りに配置されなければなりません。また、$(0、l、r)$と$
(1、l、r)$の場合、そのトリプルの2つの文字はインデックス$ l $と$ r $に配置する必要があります。

次に、削減の考え方は次のとおりです。

エッジを表現するために、$(0、l、r)$、$(1、l、r)$の組を使用します。エッジは、インデックス$ l $とインデックス$
r $のエンドポイント間を移動します。有効なトリプルリストを生成すると仮定すると、これら2つのトリプルからの文字は$ l $と$ r
$に配置する必要があります。したがって、それらの配置順序をエッジの方向を示すものとして扱うことができます。ここで$ 1
$はエッジの「頭」で、$ 0 $は「尾」です。つまり、$ 1 $を$ r $に置くと、エッジは$ l $から$ r $を指し、$ 1
$を$ l $に置くと、エッジは$ r $から$ l $を指します。

頂点を表現するために、$ x $または$ y
$文字をインデックスに置き、次の3文字を頂点に接する3つの辺の端点として使用します。 $ x $を置くと、有限言語$ A
$の文字列のために、頂点の3つの辺がすべて同じ方向(頂点のすべてまたは頂点のすべて)を指す必要があることに注意してください。そのような頂点は、外れ値$
0 $または$ 3 $を持つので、$ {0,3 } $とラベル付けされた頂点に対して$ x $を正確に配置します。 $ y
$を配置すると、$ A $の文字列のため、頂点の3つの辺のうちの1つが同じ方向を指していなければなりません。このような頂点は、外れ値$
1 $を持つので、$ {1 } $とラベル付けされた頂点に対して$ y $を正確に配置します。

ある意味で、私たちはやっています。特に、このインスタンスを解決することとグラフオリエンテーションインスタンスを解決することとの対応は明確でなければなりません。残念なことに、生成するトリプルのリストは有効ではない可能性があります。したがって、記述された「エッジ」が意図したとおりに機能しない可能性があります。特に、トリプルからの間隔が常に互いに含まれていなければならないという条件が成立しない可能性があるため、トリプルのリストは有効ではない可能性があります。

これに対処するために、さらにインフラストラクチャを追加します。特に、「クロスオーバ頂点」を追加します。交叉頂点は次数が$ 4
$の頂点であり、各ペア内で1つの辺が交叉頂点と1つの頂点を指すように辺がペアになっている。言い換えれば、クロスオーバ頂点はちょうど2つの「交差」エッジと同じように動作します。文字$
c $をあるインデックス$ i $に置くことによって、クロスオーバ頂点を表します。言語$ A $は、$ i-1 $と$ i + 2
$の文字を反対に($ 0 $と$ 1 $)、そして$ i-2 $と$ i
+反対にする。したがって、これらのインデックスをクロスオーバ頂点の4つのエッジの端点として使用すると、動作は前述のとおりです。つまり、4つのエッジがペアになり、各ペアの間で1つのポイントが1つずつポイントされます。

How do we actually place these crossovers? Well suppose we have
two intervals $(l, r)$ and $(l’, r’)$ which overlap. WLOG, $l <
l’ < r < r’$. We add the crossover character into the middle
(between $l’$ and $r$). (Let’s say that all along we spaced
everything out so far that there’s always enough space, and at the
end we will remove any unused space.) Let the index of the
crossover character be $i$. Then we replace the four triples $(0,
l, r)$, $(1, l, r)$, $(0, l’, r’)$, and $(1, l’, r’)$ with eight
triples with two each (one with character $0$ and one with
character $1$) for the following four intervals $(l, i-1)$, $(i+2,
r)$, $(l’, i-2)$, $(i+1, r’)$. Notice that the intervals don’t
overlap in the bad way anymore! (After this change, if two
intervals overlap, one is strictly inside the other.) Furthermore,
the edge from $l$ to $r$ is replaced by an edge from $l$ to the
crossover vertex followed by the edge from there to $r$; these two
edges are paired at the crossover vertex in such a way that one is
pointed in and one is pointed out; in other words, the two edges
together behave just like the one edge they are replacing.

ある意味では、このクロスオーバ頂点を2つの辺(オーバーラップした間隔)の「交差していない」頂点に配置します。クロスオーバ頂点を追加しても、追加のエッジが交差することはありません。したがって、十分なクロスオーバ頂点を挿入することによって、すべての交差エッジペアをアンクロスすることができます。最終結果は依然としてグラフオリエンテーションのインスタンスに対応しますが、トリプルのリストは有効です(プロパティはすべて交差しているエッジが「交差していない」ため、すべて簡単に検証できます)。したがって、補題が適用され、実際には対応は等価です。換言すれば、この減少は正しい。


補題の証明

補題:トリプルの有効なリストの場合、$ x $、$ y $、$ c
$の文字は、トリプルによって示された通りに配置されなければなりません。また、$(0、l、r)$と$
(1、l、r)$の場合、そのトリプルの2つの文字はインデックス$ l $と$ r $に配置する必要があります。

証明:

我々は、間隔の長さによってトリプルを誘導することによって進める。特に、我々の声明は次の通りである:あるトリプルが区間長$ k
$を持つならば、任意の$ k $に対して、そのトリプル内の文字は補題に記述されているように配置されなければならない。

基本ケース:$ k = 0 $の場合、トリプルはその区間内の単一のインデックスに文字$ x $、$ y $、または$ c
$を配置する必要があります。これは、補題に記載されているのとまったく同じです。

Inductive case: assume the statement holds for any $k$ less than
some $k’$. Now consider some triple with interval length $k’$. Then
that triple must be of the form $(i, l, r)$ with $r = l+k’-1$ and
$i in {0,1}$. The triple $(1-i, l, r)$ must also be present. The
number of triples $(alpha’,l’,r’)$ with $l le l’le r’ le r$ is
exactly $r-l+1 = k’$. These triples include triples $(0, l, r)$ and
$(1, l, r)$ but also $k’-2$ other triples of the form
$(alpha’,l’,r’)$ with $l < l’ le r’ < r$. These other
triples all have interval length smaller than $k’$, so they all
must place their characters as specified in the lemma. The only way
for this to occur is if these triples place characters in every
index starting at index $l+1$ and ending at index $r+1$. Thus, our
two triples $(0, l, r)$ and $(1, l, r)$ must place their characters
at indices $l$ and $r$, as described in the lemma, concluding the
inductive case.

誘導によって、補題は正しい。

返信を残す

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