Reorganizar una secuencia de números reales para satisfacer las desigualdades polinomiales

Question

Suponga que solucionamos un grado $ D $ polinomios $ f $ de $ k $ variables. (Si ayuda, deje que $ T $ sea el número de términos en $ F $). Considere una lista de números reales $ a_1, ldots, a_n $, ¿existe una permutación $ pi $, de modo que para todos $ i leq nk $ $$ f (a _ { pi (i)}, a_ { pi (i+1)}, ldots, a _ { pi (i+k-1)}) geq 0 $$

¿Qué tan difícil es este problema?

Answer 1

Supongamos que los números $ a_1, ldots, a_n $ son enteros, de modo que el problema está en np para cualquier $ f $ fijo. Construimos un polinomio $ f $ para que el problema sea NP-complete, por reducción de la cubierta de vértice en gráficos cúbicos ($ 3 $ -gráficos regulares).

Deje que la instancia de la cubierta del vértice cúbico consiste en un gráfico cúbico $ g = (v, e) $ y un entero $ m $, y deje $ | v | = n $. Elija los primeros $ n $ primos más grandes que $ 7 $, $ p_1, ldots, p_n $. Construimos la siguiente secuencia $ mathbf {a} $:

• Para cada borde $ (i, j) $, los números $ p_i, p_j, p_ {ij} $
• Para cada vértice $ i $, los números $ p_i, p_i^3 $
• $ m $ copias de $ 3 $
• $ nm $ copias de $ 5 $
• $ 9n/2 $ copias de $ 2 $
• $ 11 $ copias de $ 7 $

Tenga en cuenta que algunos números aparecen más de una vez. La secuencia de solución prevista consta de once copias de $ 7 $ seguido de $ n $ segmentos de longitud $ 12 $ de las siguientes dos formas: $$ 5, p_i, p_i^3,2,2,2,2,2 ,2, 2,2,2 $$ Donde $ 1 leq i leq n $, o $$ 3, p_i, p_i^3, x_1, y_1, z_1, x_2, y_2, z_2, x_3, y_3, z_3 $$ donde $ 1 Leq i leq n $ y por $ alpha in {1,2,3 } $, $$ x_ alpha, y_ alpha, z_ alpha = 2,2,2 quad text {o} quad p_i, p_ip_j, p_j text {para algún borde} (i, j). $$ una secuencia de esa forma codifica una cubierta de vértice dada por los vértices que aparecen en la segunda posición en segmentos de la segunda forma. Debe quedar claro que tal secuencia existe si y solo si existe una cubierta de vértice. Queda por mostrar cómo podemos probar que una secuencia es de esa forma utilizando un solo polinomio $ f $ que se "ejecuta" en todos trozos de longitud $ 12 $.

Dejamos $ f = -f '$, donde la función $ f' (u, v, w, x_1, y_1, z_1, x_2, y_2, z_2, x_3, y_3, z_3) $ es una función no negativa que alcanza Cero en las entradas exactamente de las siguientes formularios:

• $ 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 $ y $ x_1 = y_1 = z_1 = x_2 = y_2 = z_2 = x_3 = y_3 = z_3 = 2 $
• $ u = 3 $, $ w = v^3 $ y por cada $ alpha in {1,2,3 } $, ya sea $ x_ alpha = y_ alpha = z_ alpha = 2 $ o $ x_ alpha = v $ y $ y_ alpha = x_ alpha z_ alpha $

Este polinomio se puede construir utilizando las siguientes tres reglas:

• Una condición $ i = j $ está representada por $ (i - j)^2 $
• Dados dos polinomios no negativos para las condiciones $ c_1, c_2 $, la condición $ c_1 lor c_2 $ está representada por $ c_1 c_2 $
• Dados dos polinomios no negativos para las condiciones $ c_1, c_2 $, la condición $ c_1 land c_2 $ está representada por $ c_1 + c_2 $

Deje que $ mathbf {b} $ sea una permutación de $ mathbf {a} $ para el cual su condición es válida. Dado que $ F '$ no es negativo, debe ser que una de las condiciones anteriores se mantenga para cada segmento de longitud $ 12 $. En particular, cualquier segmento de longitud $ 12 $ debe contener $ 3 $ o $ 5 $ en alguna parte. Teniendo en cuenta el número de estos en comparación con la longitud de la secuencia, vemos que su forma general es: once elementos arbitrarios seguidos de $ N $ segmentos que comienzan con $ 3 $ o $ 5 $. Cada segmento que comienza con $ 5 $ es del formulario $$ 5, Q, Q^3,2,2,2,2,2,2,2,2,2. $$ Concluimos que $ q = p_i $ por unos $ 1 leq i leq n $. Cada segmento que comienza con $ 3 $ es de la forma $$ 3, Q, Q^3, X_1, Y_1, Z_1, X_2, Y_2, Z_2, X_3, Y_3, Z_3. $$ Como antes, $ q = p_i $ por unos $ 1 leq i leq n $. Además, por cada $ alpha in {1,2,3 } $, $ x_ alpha = y_ alpha = z_ alpha = 2 $ o $ x_ alpha = p_i $ y $ y_ alpha = p_i z_ alpha $. En el último caso concluimos que $ z_ alpha = p_j $ y $ y_ alpha = p_ip_j $ por algún borde $ (i, j) $.

En ambos casos, ninguno de los elementos en los segmentos es igual a $ 7 $, y concluimos que los primeros once elementos en la secuencia deben ser de $ 7 $. Sea $ s $ el conjunto de $ i $ de modo que haya un segmento del formulario $ 3, p_i, ldots $. Dado que hay exactamente $ m $ copias de $ 3 $, $ | S | = m $. Por cada borde $ (i, j) $, el número $ p_ {ij} $ aparece en algún lugar, y el único lugar legal es un segmento de $ 3 $. Concluimos que $ S $ es una cubierta de vértice de longitud $ m $.

Esto muestra que si su condición se mantiene, el gráfico tiene una cubierta de vértice de tamaño $ m $. Por el contrario, si el gráfico tiene una cubierta de vértice de tamaño $ M $, entonces podemos construir una secuencia que satisfaga su condición asignando cada borde a uno de los vértices que lo cubre. Esto prueba la validez de la reducción. La reducción también es el tiempo polinomial (tenga en cuenta que las primas $ P_1, ldots, P_n $ se pueden encontrar usando la fuerza bruta), lo que demuestra que su problema es NP-Hard y, por lo tanto, NP-Complete.