たとえば「π を N 桁まで計算するための計算量の下限」のような問題にアプローチする手法ってどれくらい確立されているんだろう。いや、 π は例として難しすぎるのかもしれないけれど、何らかの実数値計算の計算量に対するアプローチ。
そもそも整数乗算の計算量ですら下限は証明されていない。 2019 年の O(N log N) という結果が最新で、これは optimal ではないかと予想されているらしい。
Integer multiplication in time O(n log n) (未読)
FFT を使った乗算って正確には O(N log N) ではないんだ。というか、この論文に π についての言及もあった。
Theorem 1.1 has many immediate consequences, as many computational problems may be reduced to integer multiplication. For example, the theorem implies that quotients and k-th roots of real numbers may be computed to a precision of n significant bits in time O(n log n), that transcendental functions and constants such as e^x and π may be computed to precision n in time O(n log^2 n), and that the greatest common divisor of two n-bit integers may be found in time O(n log^2 n) [5].
へえええ。