多項式の不平等を満たすために一連の実数を再配置する

Question

$ k $変数の$ d $多項式$ f $を修正すると仮定します。 （それが役立つ場合は、$ t $を$ f $の用語数とします）。実数$ a_1、 ldots、a_n $のリストを考えてみましょう。すべての$ i leq $ $$ f（a _ { pi（i）}、a_ {{a _ { pi（i）}のすべての場合、順列$ pi $が存在します。 pi（i+1）}、 ldots、a _ { pi（i+k-1）}） geq 0 $$

この問題はどれくらい難しいですか？

Answer 1

数字$ a_1、 ldots、a_n $が整数であると仮定してください。そのため、問題は固定$ f $のnpにあります。 1立方グラフの頂点カバーから削減することにより、問題がNP完全になるように多項式$ f $を構築します（$ 3 $ -RERNILEグラフ）。

立方頂点カバーのインスタンスは、立方体グラフ$ g =（v、e）$と整数$ m $で構成され、$ | v | = n $。 $ 7 $、$ p_1、 ldots、p_n $を超える最初の$ n $ primesを選択します。次のシーケンス$ mathbf {a} $を構築します。

• 各エッジ$（i、j）$、数字$ p_i、p_j、p_ {ij} $
• 各Vertex $ i $について、数字$ p_i、p_i^3 $
• $ m $ $ 3 $のコピー
• $ nm $ $ 5 $のコピー
• $ 9N/2 $ 2 $ 2 $のコピー
• $ 11 $ $ 7 $のコピー

いくつかの数字が複数回表示されることに注意してください。意図されたソリューションシーケンスは、7ドルの11コピーに続いて、次の2つのフォームの長さ12ドルの$ n $セグメントで構成されています：$$ 5、P_I、P_I^3,2,2,2,2,2,2、 2,2,2 $$ $ 1 leq i leq n $、または$$ 3、p_i、p_i^3、x_1、y_1、z_1、x_2、y_2、z_2、x_3、y_3、z_3 $$ where $ 1 leq i leq n $ and for $ alpha in {1,2,3 } $、$$ x_ alpha、y_ alpha、z_ alpha = 2,2,2 quad text {or} quad p_i、p_ip_j、p_j text {for ance edge}（i、j）頂点カバーが存在する場合にのみ、そのようなシーケンスが存在することは明らかです。 「実行」されている単一の多項式$ f $を使用して、その形式のシーケンスがその形式であることをテストする方法を示すことは残っています。 すべて 長さ12ドルのチャンク。

$ f = -f '$、ここで、関数$ f'（u、v、w、x_1、y_1、z_1、x_2、y_2、z_2、x_3、y_3、z_3）$を達成する非陰性関数です次のフォームの正確な入力でゼロ：

• $ 3 in {v、w、x_1、y_1、z_1、x_2、y_2、z_2、x_3、y_3、z_3 } $
• $ 5 in {v、w、x_1、y_1、z_1、x_2、y_2、z_2、x_3、y_3、z_3 } $
• $ u = 5 $、$ w = v^3 $および$ x_1 = y_1 = z_1 = x_2 = y_2 = z_2 = x_3 = y_3 = z_3 = 2 $
• $ u = 3 $、$ w = v^3 $および各$ alpha in {1,2,3 } $、$ x_ alpha = y_ alpha = z_ alpha = 2 $または$ x_ alpha = v $ and $ y_ alpha = x_ alpha z_ alpha $

この多項式は、次の3つのルールを使用して構築できます。

• 条件$ i = j $は$（i -j）^2 $で表されます
• 条件$ c_1、c_2 $の2つの非陰性多項式を考えると、条件$ c_1 lor c_2 $は$ c_1 c_2 $で表されます
• 条件$ c_1、c_2 $の2つの非陰性多項式を考えると、条件$ c_1 land c_2 $は$ c_1 + c_2 $で表されます

$ mathbf {b} $を、あなたの状態が保持する$ mathbf {a} $の任意の順列とします。 $ f '$は非陰性であるため、上記の条件の1つが長さ12ドルの各セグメントに対して保持されているに違いありません。特に、長さ12ドルのセグメントには、どこかに$ 3 $または$ 5 $が含まれている必要があります。シーケンスの長さと比較したこれらの数を考慮すると、その一般的な形式は次のとおりです。11ドル$ $ n $セグメントが$ 3 $または$ 5 $で始まる$ n $セグメントが続きます。 $ 5 $から始まる各セグメントは、$$ 5、q、q^3,2,2,2,2,2,2,2,2のフォームです。 $$ $ 1 leq i leq n $の$ q = p_i $であると結論付けます。 $ 3 $で始まる各セグメントは、$$ 3、q、q^3、x_1、y_1、z_1、x_2、y_2、z_2、x_3、y_3、z_3の形式です。 $$前と同様、$ q = p_i $ for $ 1 leq i leq n $。さらに、各$ alpha in {1,2,3 } $、$ x_ alpha = y_ alpha = z_ alpha = 2 $または$ x_ alpha = p_i $および$ y_ alpha = p_i z_ alpha $。後者の場合、$ z_ alpha = p_j $および$ y_ alpha = p_ip_j $ for Edge $（i、j）$であると結論付けます。

どちらの場合も、セグメント内の要素は$ 7 $に等しくなく、シーケンス内の最初の11の要素は$ 7 $でなければならないと結論付けます。 $ s $を$ i $のセットとし、フォーム$ 3、p_i、 ldots $のセグメントがあります。正確に$ m $ $ 3 $、$ | s | = m $。すべてのエッジ$（i、j）$の場合、数字$ p_ {ij} $がどこかに表示され、唯一の合法的な場所は$ 3 $セグメントです。 $ s $は長さ$ m $の頂点カバーであると結論付けています。

これは、条件が当てはまる場合、グラフにはサイズ$ m $の頂点カバーがあることを示しています。逆に、グラフにサイズ$ m $の頂点カバーがある場合、各エッジをカバーする頂点のいずれかに割り当てることにより、状態を満たすシーケンスを構築できます。これは、削減の妥当性を証明します。また、減少は多項式時間です（プライム$ p_1、 ldots、p_n $はブルートフォースを使用して見つけることができます）。