ワトソン・クリック回文を認識する際の空間の複雑さ

Question

次のアルゴリズムの問​​題があります。

ワトソン・クリック回文である DNA 文字列を認識する空間チューリング複雑度を決定します。

ワトソン・クリック回文は、元の文字列を逆補数にした文字列です。の 補体 DNA からインスピレーションを得て、文字ごとに定義されています。A は T の補数であり、C は G の補数です。WC 回文の簡単な例は ACGT です。

これを解決する方法を 2 つ考え出しました。

1 つは $\mathcal{O}(n)$ スペースを必要とします。

• マシンが入力の読み取りを完了したら。入力テープは逆の順序で作業テープにコピーする必要があります。
• 次に、マシンは入力テープと作業テープを左から読み取り、各エントリを比較して、作業テープ内のセルが入力内のセルの補数であることを確認します。これには $\mathcal{O}(n)$ スペースが必要です。

もう 1 つは $\mathcal{O}(\log n)$ スペースを必要とします。

• 入力を読みながら。入力テープ上のエントリの数を数えます。
• 入力テープの読み取りが完了したとき
  • 手紙の補足部分を作業テープにコピーする
  • 文字 L を作業テープの最後にコピーします
• (ループポイント) カウンタ = 0 の場合、ワークテープをクリアして「yes」と書き込み、停止します。
• 入力テープが L の場合
  • 入力ヘッドをカウンターで示された回数だけ左に移動します (2 番目のカウンターが必要)
• 入力テープが R を読み取る場合
  • カウンタが示す回数だけ入力ヘッドを右に移動します (2 番目のカウンタが必要)
• ワークテープ上の値を保持するセルが入力テープ上の現在のセルと一致する場合
  • カウンタを 2 減らす
  • R または L がワークテープ上にあるかどうかに応じて、それぞれ左または右に 1 つ移動します
  • 現在の L または R の代わりに、L または R の補数をワークテープにコピーします。
  • ループを続ける
• 値が一致しない場合は、ワークテープをクリアして「いいえ」と書き込み、停止します。

これは、両方のカウンタ、現在の補数、および値 L または R を格納するための約 $2\log n+2$ スペースになります。

私の問題

最初の方法では、線形の時間と空間の両方が必要です。2 番目の方法では、$\frac{n^2}{2}$ 時間と $\log n$ スペースが必要です。見積もりから問題を与えられ、これら 2 つのアプローチを思いつきましたが、どちらを選択すればよいかわかりません。問題の空間の複雑さを与える必要があるだけです。

迷っている理由

私は 2 番目の方が時間の点で優れているので、それが最良の選択肢だと言いがちですが、その答えは私が幸運に恵まれてアルゴリズムを思いついたことによってのみ得られます。何かに空間の複雑さを与えたい場合、適切なアルゴリズムを思いつくのに運は必要ないようです。何かが足りないのでしょうか？空間の複雑さに対処するために、問題の解決策を考え出す必要があるでしょうか?

Answer 1

免責事項: 次のアルゴリズムは、線形未満空間の複雑さの標準モデルを使用しません (「 WP:DSPACE)、入力テープに書き込むためです。さらに、(ワトソン-クリック) 回文のセットは $\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$ にはありません。それにもかかわらず、これは多くの実用的な目的 (例:それぞれの文字が char C）。

問題に特定の空間複雑性があることを示すには、通常、その空間複雑性を備えたアルゴリズムを考え出す必要があります。これには試行錯誤が必要になるかもしれませんが、より良いアプローチは、検討している問題をよく理解し、アルゴリズムと複雑さについて十分な経験を積むことです。

この特定の例では、追加のスペースを必要とせず、$O(n^2)$ の時間計算量を必要とする 3 番目のアルゴリズムがあります。このアルゴリズムは定空間になります。

ヒント：入力によって占有されているスペースを使用できるのに、なぜ追加のスペースを使用するのでしょうか?

ヒント：zip を文字列内で前後に実行し、一度に 1 文字ずつチェックします。チューリング マシンの状態を使用して、どの文字をチェックしているかを記憶し、すでにチェックした文字を消去します。

Answer 2

質問の仕方から考えるべきことは、 上界 そして 下限 空間の複雑さについて。

最初の部分は通常、問題に対するアルゴリズムを提示することで行われますが、 に 他のよく研究された問題も機能するでしょう (間接的にアルゴリズムも生成されます)。複合的な複雑さ (時間と空間) を考慮しないため、たとえ時間が長くなったとしても、重要なのは空間だけです。つまり、$\mathcal{O}(\log n)$ の上限が見つかりました。

2 番目の部分は通常、はるかに複雑ですが、一定のスペースだけでは十分ではないことを簡単に示すことができます。そうすることで言語が規則的になるからです。$a^lb^{2l}a^l$ などでポンピング補題を使用すると、$l$ が想定されるポンピング数になります。これでも $\omega(1)$ と $\mathcal{O}(\log n)$ の間に大きなギャップが残ります。

練習法を見つけました (演習 6 を参照) それはいくつかのヒントを与えます。彼らのヒントを正しく解釈できれば、入力サイズごとに Myhill-Nerode 関係の同値クラスが多数存在することを証明してみてください。これは、長さが $n$ の $c\cdot\Gamma^{s(n)}$ 文字列以上は区別できないという議論に似ています ($\Gamma$ はテープのアルファベット、$s(n) $ 空間の複雑さ)。これにより、$\Omega(\log n)$ の下限が得られます。

---

この操作は簡単なので、文字の補数を気にする必要はないことに注意してください。そのため、通常の回文で機能するものはすべて、問題を解決するためにさらにいくつかの状態を使用して変更できます。

Answer 3

古典的である可能性が極めて高い 回文の時空間トレードオフ あなたの場合にも当てはまります。この結果は、空間 $S$ の回文を認識するチューリング マシンには $\Omega(n^2/S)$ の時間がかかる必要があることを示しています。$$ extrm{時間} imes extrm{空間} = \Omega(n^2)。$$の場合、最初のアルゴリズムには$ ts = theta（n^2）$があり、2番目のアルゴリズムは$ ts = theta（n^2 log n）$を持ちます。スペースの下限が $\Omega(\log n)$ であることもわかります。最適な上限は何か、つまり、対数空間と時間 $O(n^2/\log n)$ を使用するアルゴリズムがあるかどうか、または一般に $ の値がどれくらいになるのかを見つけることができませんでした。 S$ は時間 $\Omega(n^2/S)$ を達成できるでしょうか。演習として、2 つのアルゴリズムを補間する他のハイブリッド アルゴリズムを見つけてみることができます。