Exponential-size problems have not been investigated very well in complexity theory even though they appear in several applications. For example, approximating the solution of a partial differential equation requires one to raise an exponential-size matrix to a large power. We formally define linear algebra problems when the input vectors and matrices have size that is exponential in a parameter and have real number entries. We also investigate the computational complexity of these problems. We show that computing exponential-size inner product is in $\#\mathsf{P}$ and computing exponential-size matrix powering is in $\mathsf{FPSPACE}$, and these are both optimal. Furthermore, inspired from the partial differential equation motivation, we show some matrices can be converted into polynomials, and that computing polynomial powering is in $\#\mathsf{P}$, improving the matrix powering result for these matrices. We also show that some cases of polynomial powering are in $\mathsf{FP}$ with novel methods, and computing (not exponential-size) inner product and matrix powering can be done in sublinear space.
지수 크기 문제는 복잡도 이론에서 잘 연구되지는 않았지만 몇몇 응용에서 나타난다. 예를 들어 편미분방정식의 해를 근사하려면 지수 크기 행렬의 큰 거듭제곱을 계산해야 한다. 우리는 입력 벡터와 행렬이 어떤 모수에 대하여 지수 크기를 갖고 실수 성분을 가지는 선형대수 문제들을 형식적으로 정의한다. 우리는 해당 문제들의 계산복잡도 또한 조사한다. 우리는 지수 크기 내적 계산이 $\#\mathsf{P}$이고 지수 크기 행렬 거듭제곱 계산이 $\mathsf{FPSPACE}$이며 이들이 모두 최적임을 보인다. 또한 편미분방정식에서 얻은 영감으로 우리는 일부 행렬들은 다항식으로 변환될 수 있고 다항식 거듭제곱 계산은 $\#\mathsf{P}$임을 보인다. 이는 해당 행렬들에 대해 행렬 거듭제곱 계산에 대한 결과를 강화한다. 우리는 또한 참신한 방법으로 일부의 다항식 거듭제곱은 $\mathsf{FP}$임을 보이고 (지수 크기가 아닌) 내적과 행렬 거듭제곱이 선형 미만 공간에서 계산될 수 있음을 보인다.
