Komplexität der Überprüfung, ob lineare Gleichungen eine positive Lösung haben

7

Betrachten Sie ein lineares Gleichungssystem Ax=0, wo A ist ein n×nMatrix mit rationalen Einträgen. Angenommen, der Rang vonA ist <n. Was ist die Komplexität zu überprüfen, ob es eine Lösung hatx so dass alle Einträge von x sind strikt größer als 0 (nämlich xist ein positiver Vektor)? Natürlich kann man die Gauß-Eliminierung verwenden, aber dies scheint nicht optimal zu sein.

user29271
quelle
2
Gleichzeitig auf CSTheory gekreuzt . Bitte tun Sie dies nicht, da Ihre Frage wichtiger erscheint als andere.
Juho
Ist das "natürlich" offensichtlich? Ich kenne die verschiedenen LP-Standardformen nicht auf den ersten Blick, aber dies ist ein ziemlich allgemein aussehendes Setup.
Louis
2
Das Papier "Über positive Lösungen eines linearen Gleichungssystems" von Lloyd Dines scheint dies anzusprechen. Wenn Sie keinen Zugriff über JSTOR haben, werde ich den Artikel lesen und in einer Antwort zusammenfassen.
Patrick87
4
@ user29271 Bitte teilen Sie uns mit, ob dieses Papier Ihre Frage beantwortet. Wenn ja, könnten Sie eine Antwort mit einer kurzen Beschreibung der Technik posten ... Ich bin sicher, Sie würden viel Ruf dafür erhalten, ein so nützliches Ergebnis für die Community zu liefern.
Patrick87
2
Es ist ziemlich einfach, ein beliebiges lineares Programm für eine Machbarkeitsfrage zu nehmen (gibt es einen Punkt im Inneren eines Polytops, der durch lineare Ungleichungen gegeben ist) und es so zu manipulieren, dass es in Ihrer gewünschten Form vorliegt. Da die Machbarkeit für die lineare Programmierung genauso schwierig ist wie für die willkürliche lineare Programmierung, ist Ihr Problem so schwierig wie für ein beliebiges lineares Programm. Und es kann tatsächlich durch lineare Programmierung gelöst werden. Ich habe momentan keine Zeit, aber wenn niemand anderes dies erklärt und Sie bis Mitte nächster Woche noch keine zufriedenstellende Antwort gefunden haben, kann ich versuchen, die Details zu erklären.
Peter Shor

Antworten:

14

Erstens kann dies durch lineare Programmierung gelöst werden. Lassenx1, x2, , xnseien Sie Ihre Variablen. Das lineare Programm, das Ihre Frage löst, ist dann

maxt
unterliegt , für , .
txii=1...n
Ax=0

Wenn das Maximum 0 ist, gibt es keine positive Lösung. Wenn das Maximum (dh das lineare Programm ist unbegrenzt ), gibt es eine positive Lösung.


Zweitens kann mithilfe von Standardtransformationen für lineare Programme das Machbarkeitsproblem für ein beliebiges lineares Programm mit strengen Ungleichungen auf Ihr Problem reduziert werden. Wir beginnen mit dem Machbarkeitsproblem

Existiert so, dass ?x
Ax<b

Wir können jetzt eine neue Variable auf der rechten Seite all dieser Gleichungen und eine Ungleichung hinzufügen , um alles homogen zu machen. Für die te Gleichung haben wir jetztxn+1xn+1>0k

ak,1x1++ak,nxnbkxn+1<0 .

Dies ergibt ein äquivalentes Problem für eine neue Matrix :A

Existiert so, dass ?x
Ax<0

Als nächstes können wir die Ungleichungen in Gleichungen indem wir einige Variablen hinzufügen und verlangen . Die te Gleichung für das neue Problem wird zuyiyi>0k

ak,1x1++ak,nxn+ak,n+1xn+1+yk=0 .

Schließlich möchten wir zulassen, dass alle Variablen positiv sind. Wie machen wir das? Für jede Variable mit einem beliebigen Vorzeichen ersetzen wir durch und benötigen , .xixiziwizi>0wi>0

Das Machbarkeitsproblem ist im Wesentlichen so schwierig wie ein beliebiges lineares Programmierproblem. Daher gibt es im Allgemeinen keinen einfacheren Weg, Ihr Problem zu lösen, als die lineare Programmierung.

Peter Shor
quelle