Переставьте последовательность вещественных чисел так, чтобы они удовлетворяли полиномиальным неравенствам

Question

Предположим, мы фиксируем степень $ d $ полиномов $ f$ из $ k$ переменных.(Если это поможет, пусть $ t $ - количество терминов в $ f $).Рассмотрим список действительных чисел $ a_1,\ ldots,a_n $, существует ли перестановка $ \ pi $, такая, что для всех $ i \ leq n-k $ $$ f(a_{\pi(i)},a_{\pi(i+1)},\ldots,a_{\pi(i+k-1)}) \geq 0$$

Насколько сложна эта проблема?

Answer 1

Давайте предположим, что числа $ a_1,\ ldots, a_n $ являются целыми числами, так что проблема заключается в NP для любого фиксированного $ f $.Мы строим многочлен $ f$ так, чтобы задача была NP-полной, путем редукции из вершинного покрытия в кубических графах ($ 3 $ - регулярные графы).

Пусть экземпляр покрытия кубической вершины состоит из кубического графа $ G=(V,E) $ и целого числа $ m $, и пусть $|V| = n $.Выберите первые $ n $ простых чисел, превышающих $ 7 $, $p_1, \ldots, p_n $.Мы строим следующую последовательность $\mathbf{a}$:

• Для каждого ребра $(i,j)$ числа $p_i,p_j,p_{ij}$
• Для каждой вершины $i$ числа $p_i,p_i^3$
• $m$ копий по $3$
• $ n-m$ копий по $5$
• $9n/2$ копии по $2$
• $11$ копии по $7$

Обратите внимание, что некоторые цифры появляются более одного раза.Предполагаемая последовательность решений состоит из одиннадцати копий $ 7 $, за которыми следуют $ n $ сегментов длиной $ 12 $ следующих двух форм:либо $$ 5, p_i, p_i ^ 3,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 $$ где $1 \leq i \leq n $ и для $\ alpha \in \{1,2,3\} $, $$ x_\alpha,y_\alpha, z_\alpha = 2,2,2 \quad ext{или} \quad p_i, p_ip_j, p_j ext{ для некоторого ребра} (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 $ и $y_ \alpha=x_\alpha z_\alpha$

Этот многочлен может быть построен с использованием следующих трех правил:

• Условие $ I = J $ представлено через $(I - J)^2 $
• Учитывая два неотрицательных многочлена для условий $ C_1,C_2 $, условие $ C_1 \lor C_2 $ представлено через $C_1 C_2 $
• Учитывая два неотрицательных многочлена для условий $ C_1,C_2 $, условие $ C_1 \land C_2 $ представлено через $ C_1 + C_2 $

Пусть $\ mathbf{b}$ - любая перестановка $ \ mathbf{a} $, для которой выполняется ваше условие.Поскольку $ f '$ неотрицательно, должно быть, что одно из приведенных выше условий выполняется для каждого сегмента длиной $ 12 $.В частности, любой сегмент длиной $ 12 $ должен где-то содержать $3 $ или $ 5$.Рассматривая их количество по сравнению с длиной последовательности, мы видим, что ее общий вид таков:одиннадцать произвольных элементов, за которыми следуют $ n$ сегментов, начинающихся с $3$ или $5$.Каждый сегмент, начинающийся с $ 5 $, имеет вид $$ 5,q, q ^3,2,2,2,2,2,2,2,2.$$ Мы приходим к выводу, что $ q = p_i $ для некоторого $ 1 \ leq i \leq n $.Каждый сегмент, начинающийся с $ 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 $ для некоторого $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 $ для некоторого ребра $ (i,j) $.

В обоих случаях ни один из элементов в сегментах не равен $ 7$, и мы приходим к выводу, что первые одиннадцать элементов в последовательности должны быть равны $ 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 $ можно найти с помощью грубой силы), показывая, что ваша задача NP-сложная и, следовательно, NP-полная.