Ordnen Sie eine Abfolge von reellen Zahlen neu an, um Polynomunterschiede zu befriedigen

Question

Angenommen, wir fixieren einen Abschluss $ D $ Polynome $ f $ von $ k $ variablen. (Wenn es hilft, sei $ t $ die Anzahl der Bedingungen in $ f $). Betrachten Sie eine Liste der realen Zahlen $ a_1, ldots, a_n $, gibt es eine Permutation $ pi $, so dass für alle $ i leq nk $$ f (a _ { pi (i)}, a_ { pi (i+1)}, ldots, a _ { pi (i+k-1)}) Geq 0 $$

Wie schwer ist dieses Problem?

Answer 1

Nehmen wir an, dass die Zahlen $ a_1, ldots, a_n $ Ganzzahlen sind, damit das Problem für alle festgelegten $ f $ in NP liegt. Wir konstruieren ein Polynom $ f $, damit das Problem durch Reduktion von Scheitelpunktabdeckungen in Kubikdiagrammen ($ 3 $ $ -Reguläre Diagramme) ist.

Lassen Sie die Instanz des Kubikscheibenabdecks aus einem Kubikgraf $ g = (v, e) $ und einer Ganzzahl $ M $ bestehen und lassen Sie $ | v | = n $. Wählen Sie die ersten $ n $ Primes größer als $ 7 $, $ p_1, ldots, p_n $. Wir konstruieren die folgende Sequenz $ mathbf {a} $:

• Für jeden Edge $ (i, j) $, die Zahlen $ p_i, p_j, p_ {ij} $
• Für jeden Scheitelpunkt $ i $, die Zahlen $ p_i, p_i^3 $
• $ m $ Exemplare von $ 3 $ $
• $ Nm $ Exemplare von $ 5 $ $
• $ 9n/2 $ Kopien von $ 2 $
• $ 11 $ Exemplare von $ 7 $ $

Beachten Sie, dass einige Zahlen mehr als einmal erscheinen. Die beabsichtigte Lösungssequenz besteht aus elf Exemplaren von $ 7 $, gefolgt von Segmenten von $ n $ Segmenten mit einer Länge von 12 USD der folgenden zwei Formen: entweder $ 5, P_I, P_I^3,2,2,2,2,2, P_I, P_I^3,2,2,2,2,2,, 2,2,2 $$ wob Leq I Leq n $ und für $ alpha in {1,2,3 } $, $$ x_ alpha, y_ alpha, z_ alpha = 2,2,2 quad text {oder} quad p_i, p_ip_j, p_j text {für eine Kante} (i, j). Es sollte klar sein, dass eine solche Sequenz nur dann existiert, wenn ein Scheitelpunktabdeckung vorhanden ist. Es bleibt zu zeigen, wie wir testen können, dass eine Sequenz diese Form unter Verwendung eines einzelnen Polynom $ f $ hat, das "ausgeführt" wird alle Stücke mit Länge $ 12 $.

Wir lassen $ f = -f '$, wobei die Funktion $ f' (u, v, w, x_1, y_1, z_1, x_2, y_2, z_2, x_3, y_3, z_3) $ eine nicht negative Funktion ist, die erreicht Null auf genau Eingaben der folgenden Formen:

• $ 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 $ und $ x_1 = y_1 = z_1 = x_2 = y_2 = z_2 = x_3 = y_3 = z_3 = 2 $
• $ u = 3 $, $ w = v^3 $ und für jedes $ alpha in {1,2,3 } $, entweder $ x_ alpha = y_ alpha = z_ alpha = 2 $ oder $ x_ alpha = v $ und $ y_ alpha = x_ alpha z_ alpha $

Dieses Polynom kann unter Verwendung der folgenden drei Regeln konstruiert werden:

• Eine Bedingung $ i = j $ wird durch $ (i - j)^2 $ dargestellt
• Bei zwei nicht negativen Polynomen für die Bedingungen $ C_1, C_2 $ wird die Bedingung $ C_1 lor c_2 $ durch $ c_1 c_2 $ dargestellt
• Bei zwei nicht negativen Polynomen für die Bedingungen $ C_1, C_2 $ wird die Bedingung $ C_1 land c_2 $ durch $ c_1 + c_2 $ dargestellt

Sei $ mathbf {b} $ eine beliebige Permutation von $ mathbf {a} $, für die Ihr Zustand gilt. Da $ F '$ nicht negativ ist, muss es sein, dass eine der oben genannten Bedingungen für jedes Segment von 12 $ $ gilt. Insbesondere muss ein Segment von 12 USD $ $ 3 $ oder $ 5 $ irgendwo enthalten. In Anbetracht der Anzahl dieser im Vergleich zur Länge der Sequenz sehen wir, dass seine allgemeine Form: elf willkürliche Elemente, gefolgt von Segmenten $ N $, beginnend mit 3 USD $ oder 5 USD. Jedes Segment beginnend mit $ 5 $ hat das Formular $ 5, q, q^3,2,2,2,2,2,2,2,2,2. $$ wir schließen daraus, dass $ q = p_i $ für einige $ 1 leq i leq n $. Jedes Segment beginnend mit $ 3 $ ist aus dem Formular $$ 3, q, q^3, x_1, y_1, z_1, x_2, y_2, z_2, x_3, y_3, z_3. $$ Wie zuvor, $ q = p_i $ für einige $ 1 leq i leq n $. Darüber hinaus für jeden $ alpha in {1,2,3 } $ entweder $ x_ alpha = y_ alpha = z_ alpha = 2 $ oder $ x_ alpha = p_i $ und $ y_ alpha = p_i z_ alpha $. Im letzteren Fall schließen wir, dass $ z_ alpha = p_j $ und $ y_ alpha = p_ip_j $ für einen Edge $ (i, j) $.

In beiden Fällen beträgt keines der Elemente in den Segmenten $ 7 $, und wir kommen zu dem Schluss, dass die ersten elf Elemente in der Sequenz $ 7 $ betragen müssen. Sei $ s $ der Satz von $ i $, so dass es ein Segment des Formulars $ 3, p_i, ldots $ gibt. Da es genau $ M $ Exemplare von $ 3 $ gibt, $ | s | = m $. Für jeden Edge $ (i, j) $ erscheint die Nummer $ p_ {ij} $ irgendwo und der einzige legale Ort ist ein $ $ $ -segment. Wir schließen daraus, dass $ S $ eine Scheitelpunktabdeckung von Länge $ M $ ist.

Dies zeigt, dass, wenn Ihr Zustand gilt, im Diagramm ein Scheitelpunktabdeckung von Größe $ M $ hat. Umgekehrt können wir eine Sequenz erstellen, die Ihren Zustand erfüllt, indem wir einen der Scheitelpunkte, die sie abdecken, jede Kante zuweisen, wenn das Diagramm über ein Scheitelpunktabdeckung von $ M $ verfügt. Dies beweist die Gültigkeit der Reduzierung. Die Reduzierung ist auch die Polynomzeit (beachten Sie, dass die Primzahlen $ P_1, ldots, p_n $ unter Verwendung von Brute Force gefunden werden können), was zeigt, dass Ihr Problem NP-Hard und so NP-Complete ist.