kがサブセット合計でO（n^k）に対して定数であるかどうかをどのように知ることができますか？

Question

サブセット合計問題：数字のセットSとターゲット番号が与えられたとすると、0となります。その目的は、サブセットS’がSであり、その要素が0になるようにすることです。私はこの問題がS’のサイズが与えられれば多項式になると聞いた。
例えば、3の要素が0になるという手掛かりがある場合、複雑さはO(n^3)です。

クラスPは、多項式時間で解ける問題から成ります。例えば、ある定数がkの場合、O(n^k)で解くことができます。ここで、nは入力のサイズです。 (n^k)は、kのサブセットの数を表し、[n]であり、またはそれと同等の方法で、n要素セットから異なる要素を選択することができます。 n要素あり; a k - セットのサブセットはk要素のサブセットです。

したがって、0の合計がnであるkサブセットを検出または特定するアルゴリズムが多項式時間であるとします。私は、kがアルゴリズムの入力であり、kが3より大きい場合もあることを意味します。私たちはkと言うことができます定数または何ですか？

Answer 1

入力の問題のアルゴリズムの実行時間がO(n^k)の場合、この実行時の境界が多項式、擬似多項式、またはそれらのどれでもないかどうかはさまざまです。 kがの具体的なのような定数ならば、k=3のように定数は多項式です。 kが入力の一部である場合、実行時の境界はではなく、は多項式境界とみなされます。

ランタイム境界の概念を簡潔に説明しますhere;ただし、「多項式実行時バインド」という用語の非形式的な使用は、通常は多少乱雑です。最も正確な意味で、問題を解決するPは、のエンコーディング長で多項式で結び付けられたの実行時境界を持つことができます。これは、の場合には、Pのインスタンスの特定のエンコードに関連して、バインドもまた見られることを意味する。

さらに、通常、アルゴリズムの数値のバイナリエンコードが使用されるため、エンコードされた数値はエンコードの長さが指数関数的に増加することがあります。 が、その入力の数値で多項式に束縛されているが、入力の符号化長では境界が定められていない実行時境界がある場合、その境界は疑似多項式と簡単に説明されているようにhereと言います。

私はこれが助けてくれることを願っています。具体的な詳細は、通常、非公式の説明では不正確です。