Die dünnste Lösung für ein lineares Gleichungssystem finden

13

Wie schwer ist es, die dünnste Lösung für ein lineares Gleichungssystem zu finden?

Betrachten Sie formal das folgende Entscheidungsproblem:

Instanz: Ein lineares Gleichungssystem mit ganzzahligen Koeffizienten und einer Zahl .c

Frage: Gibt es eine Lösung für das System, bei der mindestens Variablen mit Null belegt sind?c

Ich versuche auch festzustellen, inwieweit die Abhängigkeit von . Das heißt, möglicherweise liegt das Problem in der FPT mit Parameter .ccc

Alle Ideen oder Referenzen werden sehr geschätzt.

Michael Wehar
quelle

Antworten:

12

Betrachten Sie das Problem MAX-LIN(R) die Anzahl erfüllter linearer Gleichungen über einen Ring maximieren R, der häufig NP-hart ist, zum Beispiel im Fall R=Z

Nehmen Sie ein Beispiel für dieses Problem, Ax=b wobei A eine n×m Matrix ist. Sei k=m+1 . Konstruieren Sie ein neues lineares System A~x~=b~ , wobei A~ eine kn×(kn+m) Matrix ist, x~ nun ein (kn+m) dimensionaler Vektor ist und b~ist ein dimensionaler Vektor:kn

wobeiIndien×n-Identitätsmatrix ist.

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

Man beachte, dass dieses System immer durch den Vektor erfüllt ist . Tatsächlich können die ersten m Einträge von ˜ x beliebig sein, und es gibt einen Lösungsvektor mit diesem Präfix.x~=(0bbb)Tmx~

Ich behaupte nun, dass der Bruchteil der Gleichungen von A x = b erfüllbar ist, wenn es eine spärliche Lösung von ˜ A ˜ x = ˜ b gibt, die mindestens δ n k Nullen hat. Dies liegt daran, dass jede erfüllte Zeile von A x = b k potenzielle Nullen ergibt, wenn x auf ˜ x erweitert wirdδAx=bA~x~=b~δnkAx=bkxx~

Wenn wir also die Sparsity der dünnsten Lösung für , haben wir auch δ maximiert , indem wir die Sparsity durch k dividieren .A~x~=b~δk

Deshalb glaube ich, dass Ihr Problem NP-schwer ist.

Joe Bebel
quelle
1
Cool! Ich danke Ihnen für das Teilen. Also, was denkst du, ist die Abhängigkeit von c? Glauben Sie , wir es in weniger als lösen kann Wo istndie Eingangsgröße? poly(n)(nc)n
Michael Wehar
1
Klar: Wenn wir annehmen, dass Ihnen gegeben ist, welche Elemente von x Null sind, können Sie diese Elemente einfach aus x entfernen , um ein niedrigeres Maß x 'zu erhalten, und Sie können auch die entsprechenden Spalten aus A entfernen , um A ' zu erhalten . Verwenden Sie dann die Gaußsche Eliminierung, um zu entscheiden, ob das reduzierte System A ' x ' = b durchführbar ist; Wenn ja, dann haben Sie eine spärliche Lösung gefunden. Dann versuchst du alles ( ncxxxAAAx=b möglichesA'x'. (nc)Ax
Joe Bebel
1
@ MichaelWehar Ich weiß nicht, ob dieses Problem FPT ist oder nicht
Joe Bebel
6

Das Problem ist NP-vollständig, wenn man das folgende Problem herabsetzt: Gibt es bei einer Matrix A mit ganzzahligen Einträgen und einem ganzzahligen Vektor b mit n Einträgen einen 0-1-Vektor x mit A x = b ?m×nAbnxAx=b

Für jede Koordinate des Vektors x , xix

  • führe neue Gleichungen x i + y i , k = 0 mit k = 1 , , 100 ( n + m ) , und ein 100(n+m)xi+yi,k=0k=1,,100(n+m)
  • führe neue Gleichungen x i + z i , k = 1 mit k = 1 , , 100 ( n + m ) ein . 100(n+m)xi+zi,k=1k=1,,100(n+m)

Verwenden Sie weiterhin das alte Gleichungssystem .Ax=b

Es gibt eine 0-1-Lösung für das ursprüngliche System , wenn und nur wenn das neue System eine Lösung hat, in der mindestens 100 ( n + m ) n Variablen Null sind.Ax=b100(n+m)n

Gamow
quelle
4

Dieses Problem ist in verschiedenen Einstellungen sehr schwer . Wie in den anderen Antworten auf diese Frage angegeben, ist das Problem über die ganzen Zahlen NP-vollständig.

Bei der Signalverarbeitung weisen die Matrix und die Vektoren rationale Einträge auf, und dieses Problem wird manchmal als Problem der spärlichen Rekonstruktion bezeichnet . In dieser Einstellung ist das Problem NP-vollständig (siehe Satz 1).

In der Codierungstheorie stammen die Einträge aus einem endlichen Feld, und dieses Problem wird manchmal als Maximum-Likelihood-Decodierungsproblem bezeichnet. In dieser Einstellung ist das Problem NP-vollständig und nicht in subexponentieller Zeit , wenn die Exponentialzeithypothese angenommen wird. Gemäß einer früheren Version eines Papers auf arXiv (siehe Lemma C.2 in Version 1 des Papers) ist das Problem außerdem W [1] -vollständig.

Argentpepper
quelle
Ihre Referenz für W [1] -Vollständigkeit scheint kein "Lemma C.2" zu haben.
@ RickyDemer Es gibt ein Lemma C.2 in Version 1 des Papiers, das er verlinkt hat. Version 2 scheint jedoch einen anderen Titel zu haben und wurde erst kürzlich geändert.
Michael Wehar
Dieses Lemma verwendet eine andere Parametrisierung als das OP.
Oh, ich wusste nicht, dass es eine aktualisierte Version gibt. Ich werde sie mir ansehen und meine Antwort entsprechend aktualisieren.
Argentpepper
Wie ich in meinem vorherigen Kommentar erwähnt habe, dass "Lemma eine andere Parametrisierung als das OP verwendet", bleibt die Frage des OP nach der parametrisierten Komplexität auch dann offen, wenn wir davon ausgehen, dass das Ergebnis wahr ist (obwohl es aus Version 2 entfernt wurde).