Сложность питания матрицы

Пусть - квадратная целочисленная матрица, а n - положительное целое число. Меня интересует сложность решения следующей проблемы:$M$$n$

Является ли запись в верхнем правом углу положительной?$M^n$

Обратите внимание, что очевидный подход повторного возведения в квадрат (или любого другого явного вычисления) требует, чтобы мы потенциально обрабатывали целые числа с удвоенной экспоненциальной величиной, то есть имели экспоненциально много битов. Однако проблема легко видна в классе «PosSLP» Аллендера и др. ( «О сложности численного анализа», SIAM J. Comput. 38 (5) ), и, следовательно, в четвертом уровне иерархии счета. ,

1) Можно ли поместить эту проблему питания матрицы в более низкий класс сложности?

2) Если нет, то может ли это быть PosSLP-сложным?

3) Меня особенно интересует проблема питания матриц для низкоразмерных матриц, то есть вплоть до матриц 6x6 включительно. Может ли сложность быть ниже для таких матриц?

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