You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference between those integers; i.e., if the removed integers are $b$ and $c$, you put $|b – c|$ into the set again. You keep applying the operation until you are left with only a single number. So after $n – 1$ steps the game will terminate; you need to find out what is maximum value of the single number left in the end.
I am interested in seeing any polynomial time algorithm for the problem. Currently I don't have any idea about how to solve this problem in less than $\mathcal{O}(n !)$.
If you feel that there does not any polynomial time algorithm, could you please establish in which complexity class it lies? Is it NP complete?
Summarizing the main arguments:
- You can never get more than maximum of $a_i$'s.
- It seems like the number of different terminal values are at most $2^{n – 2}$.
- Not every expression is valid. An expression corresponds to a combination of + and – signs assigned to integers in the array.
- Keeping the difference $\geq$ 0 is the main source of difficulty.
- If we assume that all the expressions are valid, then this problem can be converted to a NP complete problem: the SUBSET-SUM problem. But as not all the expressions are valid, this can give us better ideas/algorithms.
- Bill Bradley has proved the problem of finding the minimum is NP-hard and he has also shown the construction for point 2; the problem of finding the number of different terminal positions was raised by Johan Wästlund.
- Brendan McKay's comment extends the argument for finding the maximum is also NP hard. Hence currently we have managed to prove that the problem is NP hard.
Best Answer
[Edit: I had originally posted a proof that finding the minimum value was NP-hard; in the comments below, Brendan McKay pointed out how to convert that into a proof that finding the maximum value is NP-hard, which was the question asked by the original poster. I have edited this to include a complete answer to the original question.]
Let's refer to the operation of replacing two values $b,c$ in a multiset by the single value $|b-c|$ as a "contraction"; the original poster asks if it is possible to find an ordering of repeated contractions that maximizes the final value.
In this post, we begin by asking if we can find the order with the minimum possible value. Specifically, we try to determine whether the minimum value is zero or greater than zero. We will show that deciding this question is NP-complete. (We need to make it into a decision problem ("is it equal to zero?") rather than a minimization problem ("what's the smallest value?") to phrase it in terms of NP-completeness.) We then show how to convert this result into a statement about the maximum rather than minimum value.
Also, to Johan Wastlund's comment above, a slight modification of the construction gives an $O(2^{n-2})$ lower on the maximum number of distinct values that can be produced (which I'll outline at the bottom).
Determining if the minimum value is zero is clearly in NP-- we can simply (non-deterministically) guess the correct pattern of steps to produce zero. Showing that it is NP-complete takes a little more effort. We will show this by a reduction from the partition problem.
Take an instance of the partition problem with inputs $x_1,...,x_n$. We are trying to find a subset $S\subseteq \{1,...,n\}$ such that $\sum_{i\in S}x_i=\sum_{i\not\in S}x_i$.
Set $M_1=M_2=2\sum_i x_i$. Consider the multiset $\{M_1,M_2,x_1,...,x_n\}$. Let $f(x,y)=|x-y|$. Since we have taken $M_1$ to be so large, it follows that
$$f(\cdots(f(f(M_1,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_1-\sum_{j=1}^k x_{i_j}$$
and similarly for $M_2$.
Claim: if there exists a subset $S$ that partitions the integers $x_1,...,x_n$, then the minimum value attained by repeated contractions is zero.
Proof: Assume that such an $S$ exists. Then we can apply $f$ to $M_1$ and the elements of $S$ to get
$$M_1-\sum_{i\in S}x_i$$
and similarly with $M_2$ and the complement of $S$ to get
$$M_1-\sum_{i\not\in S}x_i$$
As our last step, we can subtract these and get zero. Since the output value is non-negative, then the minimum value is zero.
Claim: if an ordering of repeated contractions produces a final value of zero, then we can produce a partition from this ordering in polynomial time.
Proof: The computation of the final value attained by the repeated contraction corresponds to the evaluation of $f$ on a binary tree with the leaf nodes labeled by $x_1,...,x_n$. As pointed out in the comments above, we can "squash" this tree (in $O(n)$ time) and show that the output is equal to the sum $\sum_i \pm x_i$. If we let $S$ correspond to the $x_i$ with a positive index, we have constructed the desired partition.
We have shown above that determining whether the smallest value is zero is NP-complete. We now show that this implies the same complexity for the maximum.
Specifically, take $x_1,...,x_n$ and observe that the maximum possible value that can be achieved by repeated contraction is $\max_i x_i$. We now ask the question: is the maximum final value achieved by repeated contraction equal to $\max_i x_i$, or is it strictly smaller?
We will show that deciding this question is NP-complete. It is clearly in NP, since we can exhibit an ordering of contractions that achieves the maximum, if such an ordering exists.
To show that it is NP-complete, we will reduce from the problem of determining if there is an ordering of repeated contractions that equals zero.
Take the multiset $A=\{x_1,...,x_n\}$ and consider a new element $M=1+\sum_i x_i$. Let $B=A\cup \{M\}$. Note that $M$ is the unique maximum over $B$.
We first show that if the maximum final value for the repeated contraction of $B$ is $M$, then the minimum repeated contraction of $A$ is 0. If there exists a repeated contraction with final sum $M$, then any contraction that involves $M$ must be of the form $f(M,0)$ (otherwise the final sum would be strictly less than $M$) and vice versa. Suppose that we replace $M$ by 0; the same pattern of contractions will now produce a final value of 0. Therefore, we have produced a pattern of contractions on $A\cup \{0\}$ that gives a final value of zero.
In the other direction, we show that if the minimum final value for the repeated contraction of $A$ is 0, then the maximum value for $B$ is $M$. Suppose that the minimum repeated contraction of $A$ is 0. Then consider the identical pattern of contractions on $B$, which will leave us with $M$ and 0; the last contraction will produce $|M-0|=M$
Therefore, we can determine if the minimum final value of $A$ (which was arbitrary) is zero if an only if we can determine if the maximum final value of $B$ is $M$.
Therefore, the problem of determining if the maximum final value of a repeated contraction is equal to the maximum of the original set is NP-complete.
Johan Wastlund asked, as a function of $n$, what the maximum number of distinct values can be produced by applying $f$ in all possible combinations? He suggested it might be $2^{n-2}$. The construction above can be modified to show that there are at least this many possibilities.
Let $x_i=2^i$, for $i=1,...,n-2$. Let $M_1=2^{n-1}$ and let $M_2=2^n$. Since
$$M_z>\sum_{i=1}^{n-2}$$
(for $z=1,2$) then we still have $$f(\cdots(f(f(M_z,x_{i_1}),x_{i_2}),\cdots),x_{i_k})=M_z-\sum_{j=1}^k x_{i_j}$$
Let $S$ be the subset of indices subtracted from $M_1$. Then we can construct the sum $$f(M_1-\sum_{i\in S}^k x_{i},M_2-\sum_{i\not\in S}^k x_{i})= M_2-M_1+(\sum_{i\in S}^k x_{i})-(\sum_{i\not\in S}^k x_{i})$$
This sum assumes a distinct value for each subset $S$ of $\{1,...,n-2\}$, so there are at least $2^{n-2}$ distinct values.