7

この質問は純粋に好奇心からです。私は夏の間学校を休んでおり、楽しみのためにこれを解決するアルゴリズムを実装するつもりでした。それが上記の質問につながりました。この問題はどれくらい難しいですか?

問題: 正の整数のリスト、一連の数学演算子、および等号 (=) が与えられます。整数 (同じ順序で) と演算子 (何回でも) を使用して有効な数式を作成できますか?

例は、質問を明確にする必要があります。

指定: {2, 3, 5, 25} , {+, -, *, /} , {=}
出力: はい

式（私が思うのは1つだけ）は（2 + 3）* 5 = 25です。YES / NOを出力するだけで済みます。

問題はNPにあると思います。これは決定問題 (YES/NO の答え) であり、それを決定する非決定論的ポリ時間アルゴリズムを見つけることができるためです。

を。整数の間に配置する一連の演算子を非決定論的に選択します。
b. 答えが有効な数式であることを確認してください (これは一定の時間で行うことができます)。

この場合、大きな問題はこれです: 問題は P にありますか? (つまり、それを決定する決定論的なポリ時間アルゴリズムはありますか?) または問題の NP は完全ですか? (つまり、既知の NP 完全問題をこれに還元できますか? または同等に、すべての NP 言語のポリ時間はこの問題に還元できますか?) またはどちらでもない? (つまり、NP に問題がありますが、NP 完全ではありません)

注: この問題文は、P が NP と等しくないことを前提としています。また、スタック オーバーフローは初めてですが、homework タグには慣れています。これは確かに単なる好奇心であり、宿題ではありません:)

4

7 に答える 7

6

分割問題(NP-Complete)からの簡単な還元- N 個の整数 S のセットが与えられた場合、「有効な数学」問題への入力は - S の要素、N-2 '+' 演算子、および ' =' 記号。

于 2009-06-10T14:41:03.177 に答える
2

OK、最初に整数の「セット」を指定しますが、セットは定義上順序付けされていないため、整数の「リスト」を意味します。

また、ここで間違っている可能性があるという仮定を立てます。つまり、= 記号は、リストの最後から 2 番目と最後の整数の間に常に 1 回だけ現れるということです。途中で等号を許可すると、さらに複雑になります。

これは、「有効な数式」(VME) が NP 完全であることの実際の証明です。Subset sumから削減できます。ウィキペディアのサブセット合計の定義では、サブセットが空でないことが必要であることに注意してください。実際、空のサブセットを許可するサブセット合計のより一般的な問題は、目的の合計が入力の一部でもある場合、NP 完全であることは事実です。求められない限り、その証拠は出しません。サブセット sum のインスタンス{i_1, i_2, ..., i_n}と目的の sumsを指定して、VME​​ の次のインスタンスを作成します。

{0, i_1, 0, i_2, 0, ..., i_n, s}, {+, *}, {=}

サブセット合計のインスタンスが解ける場合、加算して 0 になる整数のサブセットが存在します。整数i1が合計の一部である場合は、それに対応するゼロを (すぐ左に) 追加し、合計のi1一部でない場合は、合計する、掛ける。各ゼロと右側の項の間に追加記号を挿入します。

ウィキペディアの例を挙げる

{−7, −3, −2, 5, 8}

{ −3, −2, 5}合計が 0 の場合、次のようにエンコードします。

{0, -7, 0, -3, 0, -2, 0, 5, 0, 8, 0}

結果の式は次のようになります

{0*7 + 0 + -3 + 0 + -2 + 0 + 5 + 0*8 = 0}

ここで、VME のこのインスタンスの解が部分集合和のインスタンスの解になることも示す必要があります。これは思ったより簡単です。結果の式を見ると、数値を 0 で乗算されたもの (チェーン乗算の一部として含む) とそうでないものにグループ化できます。ゼロで乗算された数値は、最終的な合計には含まれません。ゼロで乗算されていない数値は、最終的な合計に追加する必要があります。

したがって、VME​​ のこのインスタンスは、対応するサブセット和のインスタンスが解ける場合にのみ解けることを示したので、リダクションは完了です。

EDIT：パーティションの削減（コメント付き）も同様に機能し、等号をどこにでも配置できるため、より優れています。きちんとした！

于 2009-06-10T15:49:25.723 に答える
2

NP完全性をチェックする方法について、ある種の混乱があるようです。NP 完全問題は、特定の意味で、少なくとも NP の他の問題と同じくらい難しいです。一部のポスターがやろうとしているように、3SAT と比較しているとします。

さて、与えられた問題を 3SAT に還元しても何も証明されません。したがって、3SAT を効率的に解くことができれば (P=NP を意味する)、与えられた問題を効率的に解くことができます。ただし、与えられた問題が効率的に解けるとすれば、おそらくそれは 3SAT の簡単な特殊なケースにしか対応しないでしょう。

3SAT を与えられた問題に還元する必要があります。これは、与えられた問題の解が 3SAT 問題の解き方を教えてくれるように、任意の 3SAT 問題を与えられた問題の例に変換するルールを作成する必要があることを意味します。これは、3SAT が与えられた問題よりも難しくないことを意味します。3SAT は可能な限り難しいので、与えられた問題も可能な限り難しいものでなければなりません。

パーティションの問題からの削減が機能します。その問題は次のように機能します: 整数の集合 S が与えられた場合、これを 2 つの互いに素な部分集合に分割し、それらの間に S の各メンバーが含まれるようにして、互いに素な部分集合の合計が等しくなるようにできますか?

これを行うには、0 で始まり、S の各要素を含み、次に 0 を含むシーケンスを構築します。演算セットとして {+, -} を使用します。これは、S の各要素が加算または減算されて合計が 0 になることを意味します。つまり、加算された要素の合計は、減算された要素の合計と同じになります。

したがって、この問題は少なくとも分割問題と同じくらい難しいです。なぜなら、与えられた分割プログラムを解くことができれば、例の分割プログラムを解くことができ、したがって NP 完全であるからです。

于 2009-06-10T16:25:13.843 に答える
1

NP Complete であるために満たす必要がある 2 つのプロパティがあります。

次の場合、決定問題 C は NP 完全です。

  1. C は NP であり、
  2. NP のすべての問題は、多項式時間で C に還元できます。

NP のすべての問題は 3SAT に還元可能であり、3SAT は現在の問題に還元可能であるという事実から、1.2 の結果を確立しました。

したがって、NP完全です。

（編集）以下のコメントへの回答：

SAT は現在の問題に還元可能であることを証明します。3SAT は SAT に還元可能であるため、結果は次のようになります。

入力式は、次の式の結合です。

(x 1 V x 2 V x 3 V ... x n V y 1 )

(x 1 V x 2 V x 3 V ... x n V y 2 )

(x 1 V x 2 V x 3 V ... x n V y 3 )

.

.

.

(× 1V × 2V × 3V …× nV × 64 )

ここで、各 y iは、すべての x iの間に適用される演算子の順序に基づくブール値です。つまり、y iは合計 4x4x4x4x1 の値を取ることができます (演算子は +、-、x、/ のみであり、= は常に最後の演算子であると仮定します。これは、演算子セットが他の演算子を含むように変更された場合に変更できます)。

どの式も真でない場合、完全な式は FALSE と評価され、すべての可能な値、つまり x 1から x nを n の数値として、y 1から y 64を演算子を適用できるさまざまな方法 (これにより順序が処理されます)

この変換は POLY 時間で行われ、数式が有効である場合、指定されたブール式は満足できます。

誰でも欠陥に気づきますか？

于 2009-06-10T14:45:32.450 に答える
1

今すぐ完全な答えを出す時間はありませんが、この問題からナップザック問題への還元について説明できます。

動的計画法を使用すると、疑似多項式時間ソリューションを実現できます。これは、問題が実際に NP 完全であるという事実と矛盾しないことに注意してください。

于 2009-06-10T13:58:41.127 に答える
0

現時点では証明を行う時間は必要ありませんが、直感的には、それは P にはない可能性があることを示しています。算術の文法を定義できます。この問題は、有効な構文木があるかどうかを調べることになります。これらすべての端末を使用します。その問題はNPにあるがPの外側にあると私は信じています.

于 2009-06-10T15:50:57.810 に答える
0

これは実際には複雑さの質問に対する答えではありませんが、問題はカウントダウンの問題に少し似ています。簡単な検索でこの論文が見つかりました: http://www.cs.nott.ac.uk/~gmh/countdown.pdf

于 2009-06-10T13:49:52.203 に答える