3

たとえば、集合カバー決定問題は NP 完全問題として知られています。この問題の入力は、ユニバース U、U のサブセットのファミリ S、および整数 k () です。

私が混乱していることの 1 つは、k=1 とすると、S の各要素をチェックするだけで、明らかに時間 |S| で問題を解決できるということです。より一般的には、k が定数の場合、問題は次のようになります。 |S| の多項式時間で解かれます。このように、|S|/2、|S|/3... のように、k も |S| とともに増加する場合にのみ、時間計算量は指数関数的に高くなります。

だからここに私の質問があります：

  1. 私の現在の理解では、NP 完全問題の時間計算量の測定は、最悪のケースで測定されます。理解が正しいかどうか誰か教えてください。

  2. 私は誰かが別の問題が NP 困難であることを証明するのを見ました<U,S,|U|/3>。なぜ彼は??<U,S,|U|/3>ではなく、だけを証明したのだろうと思っています。<U,S,ARBITRARY k>そのような証拠は信頼できますか？

どうもありがとう！

4

1 に答える 1

1

時間計算量は、入力インスタンス サイズの関数として測定されます。入力インスタンスのサイズはビット単位で測定できます。入力インスタンスのサイズは、入力U、S、およびのいずれかが増加kするにつれて増加します。2nしたがって、答えようとしている問題は、たとえばビット数などのインスタンス サイズの問題とインスタンス サイズの問題を解決するのにどれくらいの時間がかかるかということnです。

したがって、単に入力インスタンス全体のサイズを大きくする必要があり、この特定のケースでは、Uand/orSおよび/orのサイズを大きくすることを意味しkます。

2 つの質問に答えるには:

  1. はい、最悪の場合の時間計算量が使用されます。入力サイズの最も難しい問題を探していて、n1 つだけではなく多くのパラメーターを増やすと (同じサイズの) 問題がおそらく難しくなることに正しく気づきました。

  2. あなたが参照している証拠を見る方が良いでしょうが、考え方はおそらく次のようになります：

    サイズ のセット カバー決定問題インスタンスの多項式縮小をn、問題のサイズ のインスタンスに与えますm。セット カバー決定問題の入力インスタンスのサイズが に増加する2n場合、縮小の結果は問題のサイズのインスタンスになります。これは、、 、および の入力サイズと問題の入力2mサイズの間に直接的な対応があるためです。USk

    したがって、 size のすべてのセット カバー決定問題インスタンスは、 size の問題インスタンスにnマップされますm。したがって、この簡約を使用してセット カバー決定問題の最も困難なインスタンスを探している場合、サイズ の問題の最も困難なインスタンスを見つけることができますm。

編集

リンクされた論文の証拠から：

証拠。任意の 3 カバー問題インスタンスを簡約します。ここでは、各サブセットが 3 つの要素を含むように、U のサブセットのファミリ S であるユニバース U が与えられ、以下を使用して U のすべてを (正確に) カバーできるかどうかを尋ねられます。 S の |U|/3 要素 - 均一なリソースとサイズ 3 のスケジュールを持つゲーム。

あなたが正しく言うように、セットカバー問題のすべてのインスタンスを彼らの問題に変換する必要があります。しかし、彼らは別の問題からの縮約を使用しています: "Computers and intractability - MR Garey, DS Johnson, 1979"で NP 完全であることが証明されている Exact 3-cover problem です。

Exact 3-Cover 問題はセット カバー決定問題に似ていますが、|U| = 3tとSの 3 要素サブセットのセットですU。

于 2014-01-06T08:57:25.183 に答える