ドロイドトレーダーの問題はNP-Completeであることを証明しています

Question

この質問は、KleinbergとTardosによるアルゴリズムデザインの第8章、演習35からのものです。

ゲームのプレイヤーは宇宙船を管理し、お金を稼ごうとしています さまざまな惑星にドロイドを購入し販売する。 $ n $ があります さまざまな種類のドロイドと $ k $ さまざまな惑星。各PLANET $ p $ 次のプロパティがあります。 $ s（j、p）\ geq 0 $ のドロイドがあります。 $ J $ $ j $ $ x（j、p）\ GEQ 0 $ それぞれ、 $ j= 1,2、\ dot、n $ 、および $ dの要求があります（j P）\ GEQ 0 $ 型 $ j $ のドロイド、 $ y（ J、P）\ GEQ 0 $ それぞれ。 （惑星が同時に両方を持たないと仮定します 単一のタイプのドロイドに対する正の供給と正の需要そう $ J $ ごとに、 $ s（j、p）$ または $ d（j、p）$ は $ 0 $ です。）

プレーヤーは、 $ z $ の単位で、$ Z $ を持つ $ s $ で始まります。 Planet $ t $ 。のセットには、特開平妄グラフ $ G $ があります。 $ s $ - のパス> $ G $ 有効なルートに対応 プレイヤー。 （Gは恣意的に長く防止するために非環式になるように選択されています ゲーム。特定の $ s $ - $ t $ path $ p $ in $ G $ では、プレーヤーは参加することができます 以下のような取引。プレーヤーがPlanetに到着するたびに $ p $ path $ p $ で、 $ s（j、p）$ のドロイドを購入することができます。 $ j $ $ x（j、p）$ それぞれのお金の単位（十分なお金がある場合 手）および/または $ d（j、p）$ droids $ j $ のドロイド $ y（j、p）$ お金の単位（だから私はあなたが複数の売買/売ることができると思います 各惑星）。プレイヤーの最終スコアは合計金額です 彼女はPlanet $ t $ に到着したときに手に持っています。

私はこの問題をいくつかのNP完全な問題よりも難しいことを証明しようとしていますが、私はかなり立ち往生しています。惑星はダッグで組織されているので、問題の「硬さ」はあなたが各惑星でさまざまな種類のドロイドを売買することができるという事実から来ると思います。また、この問題は最大化の問題であり、二次割り当て以外の多くのNP完全最大化問題を知りません。

私の思考プロセスは、ドロイドが何かを表す必要があるということです。たとえば、グラフの頂点を選択することです。それからドロイドの価格は何らかの方法で '値'を反映しています。たとえば、頂点カバーの削減の場合、頂点 $ i $ を表すドロイドはvertex の程度に等しい販売価格を持ちます。たとえば、$ i $ です。

以前の30の演習のために私にとってうまく働いたことは、問題の非常に単純なバージョンを考慮することでした。したがって、この場合、惑星が折れ線グラフであるか、または2種類のドロイドしかないか、または各惑星は1種類のドロイドを販売し、1種類のドロイドを購入する（プレイヤーに購入できるようにすることができる）。 /現金に保持しているのではなく販売。このように単純化し、他のNPの問題に似たかどうかを確認してください。そのため、頂点カバーまたは3-SATの削減になると思われる理由です。

ドロイドトレーダーの問題に縮小することを選択するか、またはこの問題を閲覧する必要がある問題（たとえば、3 satを見ることができるように見ることができます）の問題など、どのような問題もあります。 "Math-Container"> $ 2 ^ n $ 選択肢が選択されてから選択がいくつかの対照のセットを満たしていることを確認）

Answer 1

ナップザックからの単純な縮小は、またはパーティションの問題（それ自体がナップザックに縮小する）からわかります。

パーティションの問題からそれをやりましょう：

与えられた $ n $ 整数 $ s={a_1、a_2 \ ldots、a_n \} $ 全合計でさえ、合計がすべての要素の合計の半分の要素の合計であるサブセットがありますか？

だからパーティションの問題のインスタンスを与えられたとします。次のようにドロイドトレーダー問題のインスタンスを構築します。

• $ n $ の種類は、 $ s $ の整数ごとに1つあります。 $ s $ と $ t $ があります。 "Math-Container"> $ S $ $ t $ 。
• Planet $ S $ では、プレーヤーは各タイプの単一のドロイドを購入できます。 $ i $ $ A_I $ の価格で、何も売れません。
• Planet $ T $ では、プレーヤーはすべてのタイプ $ i $ のドロイドを販売することができます。 $ 2 \ cdot a_i $ 、そして何も買うことができません。
• プレーヤーは $ z $ から始まります。 $ s $ のすべての要素の合計値。

それでは、プレイヤーは $ \ sum s $ よりも多くのお金で終わらないことがあります。さらに、 $ \ frac {1} {2}を購入できる場合に限り、 $ \ sum s $ を達成できます。 \ sum s $ 最初の惑星のドロイドの価値、つまり $ s $ のサブセットが存在します。 > $ \ frac {1} {2} \ sum s $ 。

そのため、パーティション問題インスタンスの元の質問は、 $ \ sum s $ moneyが対応するドロイドトレーダーの問題に終了できるかどうかを尋ねることと同じです。

これは多項式の時間短縮であるため、これはクレームを証明しています。

Answer 2

プレーヤーがドロイドの数を売買できる場合でも、問題はNP完了です。 この問題。

$ n $ 変数 $ x_1、\ ldots、x_n $ の

$ m $ 句は、次のようなグラフを構築します。

s ---> x_1^0 --> x_2^0 ... x_n^0 ---> t
  \          \/                   / 
   \         /\                  /
    -> x_1^1 --> x_2^1 ... x_n^1

.

それは、すべてのステップで、プレーヤーは惑星の1つの標準的な1つに行くことを選択します $ x_i ^ 0 $ 、 $ x_i ^ 1 $ 。

各句 $ D_J $ 、 $ d_j '$ を構築します。 class="math-container"> $ j $ 。 $ j $ の場合は、 $ x_1 \ vee \ neg x_3 \ vee x_4 $ です。その後、Planet $ x_1 ^ 0、x_3 ^ 1 $ のタイプのDROIDは1つあります。 Planet $ x_1 ^ 1、x_3 ^ 0 $ x_1 ^ 1、x_3 ^ 0 $ x_3 ^ 0 $ x_1 ^ 1、x_3 ^ 0 $ x_3 ^ 0 $ の販売と1つのドロイドPlanet $ x_4 ^ 0 0 $ のType $ D_J $ のドロイドに対する1つの要求があります。 Planet $ x_4 ^ 1 $ のType $ d_j '$ のドロイドの要求。タイプごとに、1つのドロイドを購入するためのプレーヤーの価格が常に1で、1つのドロイドを販売するためのプレイヤーの価格は常に2です。 $ m $ $ m $ は非常に大きな数です。

今度は、 $ m + m $ のお金が $ t $ 。

この縮小は、プレーヤーがドロイドの数を売買することができるかどうかに関係なく、強くNP-Complete 。