3
$\begingroup$

Given a field $\mathbb{F}$ and a consistent underdetermined system $Ax=b$ over $\mathbb{F},$ $A\in \mathbb{F}^{m \times N}$ and $b \in \mathbb{F}^m,$ finding a vector $z \in \mathbb{F}^N$ such that $Az=b$ and $\|z\|_0 \leq \|x\|_0$ for all $x \in \mathbb{F}^N$ such that $Ax=b$ is NP-hard.

A proof exists in the literature from Simon Foucart for the cases where the base field is $\mathbb{R}$ or $\mathbb{C}.$ Although Foucart didn't prove this exact problem, but something similar, and although Foucart's work was not concerned with finite field case, I believe my interpretation and extension of Foucart's proof establishes NP-Hardness for any field of any characteristic.

What I intend to do here is to merely check this proof for validity; since I am a doctoral candidate writing my dissertation in mathematics and my since my (now retired) advisor is unfamiliar with combinatorial optimization, I figured this board would be the best place to turn for guidance on this problem, as its proof is needed for the backdrop leading to the main analysis of underdetermined systems in my thesis.

To the proof: we reduce from 3-SET-COVER, which asks whether there exists a (nonoverlapping) partition $C_j, j \in J$ within a given collection $\mathbf{C}$ of three-element subsets of some set $S,$ where $S$ has cardinality $|S|=m=3k$ for some natural number $k$ (hence without loss of generality we can refer to $S$ as the set $[m]=\{1, \ldots, m\}$ ).Papadimitriou and Steiglitz have shown that 3-SET-COVER is NP-Complete by reduction from 3-D MATCHING.

Here, $\|x\|_0$ simply means the number of nonzero components in the vector $x.$

For a given set $S$ and collection $\mathbf{C_i}, i \in [N]$ of three-element subsets of $S$ as described above, construct a matrix $A \in \mathbb{F}^{m \times N}$ with columns $a_i$ such that $a_{i,j}=1$ if j $\in C_i$ and $a_{i,j}=0$ if $j \not \in C_i.$ Additionally, let $b=\mathbf{1},$ the vector in $\mathbb{F}^m$ whose components are all equal to $1 \in \mathbb{F}.$ It is obvious this system can be constructed in polynomial time on $m$ and $N.$

Let $z$ be such that $Az=b$ and $\|z\|_0 \leq \|x\|_0$ for all $x$ such that $Ax=b.$ If $\|z\|_0 < \frac{m}{3}$ then $\|Az\|<3\cdot\frac{m}{3}=m=\|b\|_0,$ a contradiction since $\|b\|_0=m.$ Hence $\|z\|_0 \geq \frac{m}{3}.$

Run an algorithm solving for a minimal support solution of $Ax=b$ with output $z.$ There are two cases remaining: first, if $\|z\|_0 = \frac{m}{3},$ then $C_j, j \in supp(z) $ covers $[m]$ exactly. Second, if $\|z\|_0 > \frac{m}{3}$ then the collection $\mathbf{C}$ contains no subcollection covering $[m]$ exactly; if such a subcollection $C_j \subset \mathbb{C}$ existed, the $\frac{m}{3}$ corresponding columns $a_j$ add to $\mathbf{1},$ contradicting the initial assumption for the second part.

This means any algorithm solving the $\ell_0$ minimization problem solves any 3-EXACT COVER problem through a polynomial transformation, and the proof is complete.

=====

Is this proof valid? My main worry is that if $\mathbb{F}$ is a finite field, then the cyclic nature of addition could produce a cover, but the cover could not be exact, since this minimal support solution involves columns of $A$ corresponding to overlapping subsets within $\mathbf{C}$ in this case.

Thanks for any help ahead of time!

$\endgroup$

closed as off-topic by Lev Reyzin Mar 28 '17 at 21:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.