# Is this sorting problem NP-complete?

Consider array $$A=(a_1,a_2,...,a_n)$$ such that $$a_i$$s are positive integers. Moreover, we have $$k$$ binary tuples, each with length $$n$$. In each iteration, we choose one of those tuples, and decrease it from the array. For example, if $$A=(5,7,4,2)$$ and we decrease $$(1,0,0,1)$$ from it, it will become $$(4,7,4,1)$$. We cannot use a tuple more than one time. Moreover, we know that sum of all those $$k$$ tuples is $$A$$. What is the minimum number of tuples we need to decrease from $$A$$, in order that $$A$$ be sorted in decreasing order?

I want to know whether it is an NP-hard problem.

Example: $$A=[2,3,4,5]$$

tuples=$$(0,1,1,1),(0,0,1,1),(1,0,0,1),(1,0,1,1),(0,1,1,1),(0,1,0,0)$$

The answer is 4. By subtracting (0,1,1,1),(0,1,1,1),(0,0,1,1) and (1,0,0,1), we will have [1,1,1,1] which is decreasingly sorted. We used 4 tuples, and it is not possible with fewer tuples(at least, I could not).

• You have to reduce the array down to (0,0,0,0)? "...A be sorted in decreasing order" -- at each step? Feb 4 at 20:14
• Not necessarily to (0,0,0,0). For example, if you can decrease the tuples in a way that [5,7,4,2] converts to [5,5,3,1], it is feasible. Feb 4 at 21:16

You can reduce from exact-cover by $$3$$-sets (X3C): given a set $$X$$ of $$3n$$ elements $$x_1, \dots, x_n$$, and a collection $$S = \{S_1, \dots, S_m\}$$ of $$m$$ sets each containing exactly $$3$$ elements, is there an exact cover, i.e., a subset $$S'$$ of $$S$$ such that $$|S'|=n$$ and $$\cup_{S_j \in S'} S_j = X$$?

Consider the instance of your problem where:

• $$A = (a_0, a_1, a_2, a_3, \dots a_{3n}) = (3n, 3n, 3n-1, 3n-2, \dots 1)$$ is an array of length $$3n+1$$ (for ease of notation I'm indexing the array from $$0$$) where $$a_0 = 3n$$ and $$a_i = 3n-i$$ for $$i \ge 1$$
• There is a tuple $$t_j$$ for each set $$S_j$$. The $$i$$-th entry (again, indexing from $$0$$) is set to $$1$$ in $$t_j$$ if and only if $$x_i \in S_j$$.
• Suitably add a bunch of tuples, each with only a single entry set to $$1$$, in order to ensure that the sum of all tuples yields exactly $$A$$ (notice that only you need polynomially many tuples).

If there is an exact cover $$S'$$, then selecting all $$t_j$$ such that $$S_j \in S'$$ yields the array $$(3n, 3n-1, 3n-2, \dots, 0)$$.

If you can use $$n$$ tuples to transform $$A$$ into a decreasing vector, then each entry $$a_i$$ with $$i \ge 1$$ is decreased at least once. Moreover, since each tuple has at most $$3$$ entries set to $$1$$, each entry $$a_i$$ with $$i \ge 1$$ is decreased exactly once, while $$a_0$$ is never decreased. This means that the collection of sets $$S_j$$ such that $$t_j$$ is a selected tuple is an exact cover.

To summarize, there is a solution to the instance of your problem using at most $$n$$ tuples if and only if there a solution to the X3C instance.

• Sorry but I do not understand. If A=(3n,3n,3n-1,3n-2,,,,,,1), It is already sorted in decreasing order, and the minimum number of tuples needed to be subtracted from it to be sorted decreasingly is 0. Feb 4 at 21:34
• $(3n, 3n, 3n-1, \dots, 1)$ is not sorted in decreasing order because the first two entries are equal (it is sorted in non-increasing order though). If you are interested in transforming $A$ to a vector sorted in non-increasing order, then the same reduction works, you just need to start with $A= (2, 3,3,3, \dots, 3)$. Feb 4 at 21:43
• Thanks Steven. I appreciate your help. Feb 14 at 20:41