Applying a permutation on a sequence with multiplication

We are given a sequence of $n$ numbers called $\alpha$ and an arbitrary number $x$. Give an algorithm to find a permutation $\pi$ of size $n$ such that $\sum_{i=1}^n{\alpha_i.\pi_i} = x$ or tell if there is none.

Well I wasn't able to solve it in polynomial time and I'm not sure whether it's possible. So if it's NP would you give me some observations on the reason?

The problem is NP-complete. Here is a reduction from 3SAT.

Given an instance of 3SAT with variables $v_1,\ldots,v_n$ and clauses $c_1,\ldots, c_m$, construct numbers as follows. We represent a number as the form $\lambda_1p^{\mu_1}+\lambda_2p^{\mu_2}+\cdots$ where $p$ is a very large number (we will estimate $p$ later) so that we can assume there is no carry when performing addition of numbers.

• Construct $2n-1$ numbers $u_1,\ldots,u_{2n-1}$: $p^0, p^1, \ldots, p^{2n-2}$.

• For each variable $v_i$, if $v_i$ shows up in clauses $c_{j_1},c_{j_2},\ldots$ and $\bar{v}_i$ shows up in $c_{k_1},c_{k_2},\ldots$, construct two numbers $y_i=p^{2n-2+i}+mp^{3n-2+j_1}+mp^{3n-2+j_2}+\cdots$ and $\bar{y}_i=p^{2n-2+i}+mp^{3n-2+k_1}+mp^{3n-2+k_2}+\cdots$.

• For each clause $c_j$, construct numbers $z_j=p^{3n-2+j}$.

• Add $0$s to make there are $(13n+1)m$ numbers in total.

• The target

$$
\begin{align}
x=\;&(n+1)p^0+(n+2)p^1+\cdots+(3n-1)p^{2n-2}\\
&+4np^{2n-1}+4np^{2n}+\cdots+4np^{3n-2}\\
&+16nmp^{3n-1}+(16nm+1)p^{3n}+\cdots+(16nm+m-1)p^{3n-2+m}.
\end{align}
$$

Since there are $(13n+1)m$ numbers and the coefficient of $p^{\mu}$ is at most $m$, we can choose $p=(13n+1)m^2+1$. The construction is in polynomial time.

Now we can see in a valid permutation, the first $2n-1$ numbers must occupy the positions from $n+1$ to $3n-1$, and the next $2n$ numbers $y_1,\bar{y}_1,\ldots$ must occupy the positions $1,\ldots, n$ (say low positions) and $3n,\ldots, 4n-1$ (say high positions), where for each $i$, one of $y_i,\bar{y}_i$ occupies a low position and the other occupies a high position.

Suppose the instance of 3SAT is satisfiable. If $v_i$ is assigned $1$, we arrange $y_i$ at a high position and $\bar{y}_i$ at a low position; otherwise we arrange $y_i$ at a low position and $\bar{y}_i$ at a high position. Now the numbers constructed in steps 1 and 2 are arranged. Consider $\sum\alpha_i\pi_i=\cdots+\lambda_1p^{3n-2+1}+\cdots+\lambda_m p^{3n-2+m}$ for these numbers. We can arrange $z_j$ at position $16nm+j-\lambda_j$ to satisfy the sum goal. Note at least one literal in a clause must be assigned $1$, i.e. its corresponding number ($y_i$ or $\bar{y}_i$) must be at a high position, hence we have

$$m\cdot 3n (3n-1)m$. This means at least one number ($y_i$ or $\bar{y}_i$) related to clause $c_j$ is arranged a high position, which means the clause is satisfied.

For example, consider an instance with two clauses $\bar{v}_1\vee v_2\vee v_3$ and $v_1\vee \bar{v}_2\vee v_3$, the numbers are:

p^0  p^1  p^2  p^3  p^4  p^5  p^6  p^7  p^8  p^9
                                    v_1  v_2  v_3  c_1  c_2
u_1        1
u_2             1
u_3                  1
u_4                       1
u_5                            1
y_1                                 1                   2
\bar{y}_1                           1              2   
y_2                                      1         2
\bar{y}_2                                1              2
y_3                                           1    2    2
\bar{y}_3                                     1
z_1                                                1
z_2                                                     1
0
0
...
-----------------------------------------------------------
x          4    5    6    7    8    12   12   12   96   97

There are $80$ numbers in total. (One of) the permutation(s) corresponding to the solution $v_1=v_2=v_3=1$ is $\bar{y}_1\bar{y}_2\bar{y}_3u_1u_2u_3u_4u_5y_1y_2y_30\cdots 0z_1z_20\cdots$ where $z_1$ is at position $73$ and $z_2$ is at position $74$.

If the numbers are upper-bounded by a constant, say $100$, then the problem can be solved in polynomial time.

Let $f(\alpha, x)$ denote whether such permutation exists. Note for any permutation $\pi$, suppose $\alpha_k$ is placed at the first position (i.e. $\pi_k=1$), we have
$$\sum \alpha_i\pi_i=\alpha_k+\sum_{i\neq k}\alpha_i\pi_i=\sum \alpha_i+\sum_{i\neq k}\alpha_i(\pi_i-1),$$
which means the primary problem has a valid solution iff there exists $k$ such that the subproblem for sequence $\alpha-\alpha_k$ (meaning the sequence $\alpha_1,\ldots,\alpha_{k-1},\alpha_{k+1},\ldots$) and target $x-\sum \alpha_i$ has a valid solution, so we have

$$f(\alpha,x)=\bigvee_{i=1}^n f\left(\alpha-\alpha_i,x-\sum_{j=1}^n \alpha_j\right).$$

Note we do not care the order of the sequence, so every subsequence of $\alpha$ can be expressed as "$n_1$ $1$s, ..., $n_{100}$ $100$s", which means there are up to $n^{100}$ different subsequences of $\alpha$. Therefore, we can compute $f(\alpha,x)$ using the recursion formula above in $O(n\cdot xn^{100})=O(n^{103})$ time.

StackExchange Computer Science Q#95939, answer score: 3