Rearrange a sequence of real numbers to satisfy polynomial inequalities

Question

Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$). Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$, such that for all $i\leq n-k$ $$ f(a_{\pi(i)},a_{\pi(i+1)},\ldots,a_{\pi(i+k-1)}) \geq 0$$

How hard is this problem?

Answer 1

Let's assume that the numbers $a_1,\ldots,a_n$ are integers, so that the problem is in NP for any fixed $f$. We construct a polynomial $f$ so that the problem is NP-complete, by reduction from vertex cover in cubic graphs ($3$-regular graphs).

Let the instance of cubic vertex cover consist of a cubic graph $G=(V,E)$ and an integer $m$, and let $|V| = n$. Pick the first $n$ primes larger than $7$, $p_1,\ldots,p_n$. We construct the following sequence $\mathbf{a}$:

• For each edge $(i,j)$, the numbers $p_i,p_j,p_{ij}$
• For each vertex $i$, the numbers $p_i,p_i^3$
• $m$ copies of $3$
• $n-m$ copies of $5$
• $9n/2$ copies of $2$
• $11$ copies of $7$

Note that some numbers appear more than once. The intended solution sequence consists of eleven copies of $7$ followed by $n$ segments of length $12$ of the following two forms: either $$ 5,p_i,p_i^3,2,2,2,2,2,2,2,2,2 $$ where $1 \leq i \leq n$, or $$ 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 some edge } (i,j).$$ A sequence of that form encodes a vertex cover given by the vertices appearing in the second position in segments of the second form. It should be clear that such a sequence exists if and only if a vertex cover exists. It remains to show how we can test that a sequence is of that form using a single polynomial $f$ which is "run" on all chunks of length $12$.

We let $f = -f'$, where the function $f'(u,v,w,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3)$ is a non-negative function which attains zero on exactly inputs of the following forms:

• $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$ and $x_1=y_1=z_1=x_2=y_2=z_2=x_3=y_3=z_3=2$
• $u = 3$, $w=v^3$ and for each $\alpha \in \{1,2,3\}$, either $x_\alpha=y_\alpha=z_\alpha=2$ or $x_\alpha=v$ and $y_\alpha=x_\alpha z_\alpha$

This polynomial can be constructed using the following three rules:

• A condition $I = J$ is represented by $(I - J)^2$
• Given two non-negative polynomials for the conditions $C_1,C_2$, the condition $C_1 \lor C_2$ is represented by $C_1 C_2$
• Given two non-negative polynomials for the conditions $C_1,C_2$, the condition $C_1 \land C_2$ is represented by $C_1 + C_2$

Let $\mathbf{b}$ be any permutation of $\mathbf{a}$ for which your condition holds. Since $f'$ is non-negative, it must be that one of the above conditions holds for each segment of length $12$. In particular, any segment of length $12$ must contain $3$ or $5$ somewhere. Considering the number of these compared to the length of the sequence, we see that its general form is: eleven arbitrary elements followed by $n$ segments starting with $3$ or $5$. Each segment starting with $5$ is of the form $$ 5,q,q^3,2,2,2,2,2,2,2,2,2. $$ We conclude that $q = p_i$ for some $1 \leq i \leq n$. Each segment starting with $3$ is of the form $$ 3,q,q^3,x_1,y_1,z_1,x_2,y_2,z_2,x_3,y_3,z_3. $$ As before, $q = p_i$ for some $1 \leq i \leq n$. Furthermore, for each $\alpha \in \{1,2,3\}$, either $x_\alpha = y_\alpha = z_\alpha = 2$ or $x_\alpha = p_i$ and $y_\alpha = p_i z_\alpha$. In the latter case we conclude that $z_\alpha = p_j$ and $y_\alpha = p_ip_j$ for some edge $(i,j)$.

In both cases, none of the elements in the segments are equal to $7$, and we conclude that the first eleven elements in the sequence must be $7$. Let $S$ be the set of $i$ such that there is a segment of the form $3,p_i,\ldots$. Since there are exactly $m$ copies of $3$, $|S| = m$. For every edge $(i,j)$, the number $p_{ij}$ appears somewhere, and the only legal place is a $3$-segment. We conclude that $S$ is a vertex cover of length $m$.

This shows that if your condition holds then the graph has a vertex cover of size $m$. Conversely, if the graph has a vertex cover of size $m$ then we can construct a sequence satisfying your condition by assigning each edge to one of the vertices covering it. This proves the validity of the reduction. The reduction is also polynomial time (note that the primes $p_1,\ldots,p_n$ can be found using brute force), showing that your problem is NP-hard, and so NP-complete.