Seja uma matriz inteira quadrada e seja um número inteiro positivo. Estou interessado na complexidade do seguinte problema de decisão:
A entrada no canto superior direito de positiva?
Observe que a abordagem óbvia do quadrado iterado (ou qualquer outro cálculo explícito) exige que lidemos potencialmente com números inteiros de magnitude duplamente exponencial, ou seja, tendo exponencialmente muitos bits. No entanto, o problema é facilmente visto na classe "PosSLP" de Allender et al. ( "Sobre a complexidade da análise numérica", SIAM J. Comput. 38 (5) ) e, portanto, no quarto nível da hierarquia de contagem .
1) É possível colocar esse problema de alimentação da matriz em uma classe de menor complexidade?
2) Se não, poderia ser difícil para o PosSLP?
3) Estou especialmente interessado no problema de alimentação da matriz para matrizes de baixa dimensão, ou seja, até e incluindo matrizes 6x6. A complexidade pode ser menor para essas matrizes?
Respostas:
Para matrizes de tamanhos , o Problema de Positividade de Alimentação da Matriz está em P ( consulte este artigo para aparecer no STACS 2015)k=2,3 P
fonte