Złożoność zasilania macierzy

Niech będzie kwadratową macierzą liczb całkowitych, a niech n będzie liczbą całkowitą dodatnią. Interesuje mnie złożoność następującego problemu decyzyjnego:$M$$n$

Czy prawy górny wpis dodatni?$M^n$

Zauważ, że oczywiste podejście iterowanego kwadratu (lub innego jawnego obliczenia) wymaga od nas potencjalnie obsługi liczb całkowitych o podwójnie wykładniczej wielkości, tj. Mających wykładniczo wiele bitów. Jednak problem można łatwo dostrzec w klasie „PosSLP” Allendera i wsp. ( „O złożoności analizy numerycznej”, SIAM J. Comput. 38 (5) ), a zatem na czwartym poziomie hierarchii liczenia .

1) Czy można umieścić ten problem zasilania macierzy w niższej klasie złożoności?

2) Jeśli nie, to czy może być trudne PosSLP?

3) Szczególnie interesuje mnie problem zasilania macierzy dla matryc niskowymiarowych, tj. Do matryc 6x6 włącznie. Czy złożoność może być mniejsza dla takich matryc?

$k = 2,3$$\mathsf{P}$