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

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

Erstens kann dies durch lineare Programmierung gelöst werden. Lassen$x_1$, $x_2$, $\ldots$, $x_n$seien Sie Ihre Variablen. Das lineare Programm, das Ihre Frage löst, ist dann

$\max t$
unterliegt , für , .
$t \leq x_i$$i=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.$\infty$

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$
$A x < 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 jetzt$x_{n+1}$$x_{n+1} > 0$$k$

$a_{k,1} x_1 + \ldots + a_{k,n} x_n - b_k x_{n+1} < 0$ .

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

Existiert so, dass ?$x$
$A'x < 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 zu$y_i$$y_i > 0$$k$

$a'_{k,1} x_1 + \ldots + a'_{k,n} x_n + a'_{k,n+1} x_{n+1} +y_k = 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 , .$x_i$$x_i$$z_i - w_i$$z_i>0$$w_i > 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.