Trouver la solution la plus simple à un système d'équations linéaires

13

Est-il difficile de trouver la solution la plus simple à un système d'équations linéaires?

Plus formellement, considérons le problème de décision suivant:

Instance: Un système d'équations linéaires avec des coefficients entiers et un nombre c .

Question: Existe-t-il une solution au système avec au moins c variables assignées à zéro?

J'essaie également de déterminer la dépendance à l'égard de c . Autrement dit, le problème est peut-être FPT avec le paramètre c .

Toutes les idées ou références sont vraiment appréciées.

Michael Wehar
la source

Réponses:

12

Considérons le problème de maximiser le nombre d'équations linéaires satisfaites sur un anneau R , qui est souvent NP-difficile, par exemple dans le cas R = ZMAX-LIN(R)RR=Z

Prenons une instance de ce problème, A est une matrice n × m . Soit k = m + 1 . Construire un nouveau système linéaire ˜ A ˜ x = ˜ b , où ˜ A est une matrice k n × ( k n + m ) , ˜ x est maintenant un vecteur dimensionnel ( k n + m ) et ˜ bAx=bAn×mk=m+1A~x~=b~A~kn×(kn+m)x~(kn+m)b~est un vecteur dimensionnel:kn

Inest lamatrice d'identitén×n.

A~=[AInInInInInInIn],b~=[b00]
Inn×n

Notez que ce système est toujours satisfaite par le vecteur . En fait, les m premières entrées de ˜ x peuvent être arbitraires, et il existe un vecteur de solution avec ce préfixe.x~=(0bbb)Tmx~

Je prétends maintenant que la fraction des équations de A x = b est satisfiable s'il existe une solution clairsemée de ˜ A ˜ x = ˜ b qui a au moins δ n k zéros. En effet, chaque ligne satisfaite de A x = b donne k zéros potentiels lorsque x est étendu à ˜ xδAx=bA~x~=b~δnkAx=bkxx~

Ainsi, si nous trouvons la rareté de la solution la plus éparse à , nous avons également maximisé δ , en divisant la rareté par k .A~x~=b~δk

Par conséquent, je crois que votre problème est NP-difficile.

Joe Bebel
la source
1
Cool! Merci pour le partage. Alors, que pensez-vous que la dépendance à l'égard de c? Pensez-vous que nous pouvons le résoudre en moins de poly(n)(nc) where n is the input size?
Michael Wehar
1
Sure: if we assume you're given which c elements of x are zero, then you can simply remove those elements from x to get a lower dimensional x and also remove the corresponding columns from A to get A. Then use gaussian elimination to decide if the reduced system Ax=b is feasible; if it is, then you've found a sparse solution. Then, you try all (nc) possible Ax.
Joe Bebel
1
@MichaelWehar I don't know whether this problem is FPT or not though
Joe Bebel
6

The problem is NP-complete, by reduction from the following problem: Given an m×n matrix A with integer entries and an integer vector b with n entries, does there exist a 0-1 vector x with Ax=b?

For every coordinate xi of vector x,

  • introduce 100(n+m) new equations xi+yi,k=0 with k=1,,100(n+m), and
  • 100(n+m)xi+zi,k=1k=1,,100(n+m)

Ax=b

Ax=b100(n+m)n variables are zero.

Gamow
la source
4

This problem is hard, in various settings. As stated in the other answers to this question, the problem is NP-complete over the integers.

In signal processing, the matrix and the vectors have rational entries, and this problem is sometimes called the sparse reconstruction problem. In this setting, the problem is NP-complete (see Theorem 1).

In coding theory, the entries are from a finite field, and this problem is sometimes called the maximum-likelihood decoding problem. In this setting, the problem is NP-complete and not in subexponential time, assuming the exponential time hypothesis. Furthermore, according to a previous version of a paper on arXiv (see Lemma C.2 in version 1 of the paper), the problem is W[1]-complete.

argentpepper
la source
Your reference for W[1]-completeness does not appear to have a "Lemma C.2". ​ ​
@RickyDemer There is a Lemma C.2 in version 1 of the paper that he linked. However, version 2 seems to have a different title and was very recently changed.
Michael Wehar
That lemma uses a different parameterization from the OP. ​ ​
Oh I didn't realize there was an updated version, I'll take a look at it and update my answer accordingly.
argentpepper
As I mentioned in my previous comment, that "lemma uses a different parameterization from the OP", so even if we assume the result is true (despite having been removed from version 2), the OP's question about parameterized complexity would still be open. ​ ​