Is this sorting problem NP-complete?

Question

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).

Answer 1

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.