Complexidade de verificar se as equações lineares têm uma solução positiva

Considere um sistema de equações lineares $Ax=0$, Onde $A$ é um $n\times n$matriz com entradas racionais. Suponha que a classificação de$A$ é $<n$. Qual é a complexidade de verificar se ele tem uma solução$x$ de modo que todas as entradas de $x$ são estritamente maiores que 0 (ou seja, $x$é um vetor positivo)? Obviamente, pode-se usar a eliminação de Gauss, mas isso parece não ser o ideal.

Primeiro, isso pode ser resolvido por programação linear. Deixei$x_1$, $x_2$, $\ldots$, $x_n$sejam suas variáveis. O programa linear que resolve sua pergunta é então

$\max t$
sujeito a
$t \leq x_i$, para $i=1 ... n$,
$Ax = 0$.

Se o máximo for 0, não haverá solução positiva. Se o máximo é$\infty$(ou seja, o programa linear é ilimitado ), existe uma solução positiva.

Segundo, usando transformações padrão em programas lineares, o problema de viabilidade de um programa linear arbitrário com desigualdades estritas pode ser reduzido ao seu problema. Começamos com o problema de viabilidade

Existe $x$ de tal modo que
$A x < b$ ?

Agora podemos adicionar uma nova variável $x_{n+1}$ no lado direito de todas essas equações e uma desigualdade $x_{n+1} > 0$para tornar tudo homogêneo. Então, para o$k$^th equação, agora temos

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

Isso gera um problema equivalente em uma nova matriz $A'$:

Existe $x$ de tal modo que
$A'x < 0$ ?

Em seguida, podemos transformar as desigualdades em equações adicionando algumas variáveis $y_i$ e exigindo que $y_i > 0$. o$k$A equação do novo problema se transforma em

$a'_{k,1} x_1 + \ldots + a'_{k,n} x_n + a'_{k,n+1} x_{n+1} +y_k = 0$.

Finalmente, queremos permitir que todas as variáveis ​​sejam positivas. Como fazemos isso? Para cada variável$x_i$ com um sinal arbitrário, substituímos $x_i$ de $z_i - w_i$e exigem $z_i>0$, $w_i > 0$.

O problema de viabilidade é essencialmente tão difícil quanto um problema de programação linear arbitrário; portanto, em geral, não haverá maneira mais fácil de resolver seu problema do que usar a programação linear.