Dowolna obliczalna liczba transcendentalna obliczalna w czasie P, ale nie

Czy istnieje jakaś znana obliczalna liczba transcendentalna taka, że ​​jej ta cyfra jest obliczalna w czasie wielomianowym, ale nie w ?$n$$O(n)$

Oto konstrukcja takiej liczby. Możesz spierać się, czy oznacza to, że taka liczba jest „znana”.

Weź dowolną funkcję z do gdzie -ta cyfra nie jest obliczalna w czasie . Taka funkcja istnieje na przykład za pomocą zwykłej techniki diagonalizacji. Interpretuj jako$f$$\mathbb{N}$$\{ 1, 2, \ldots, 8 \}$$n$$O(n)$$f(n)$$n$dziesiąta cyfra dziesiętna jakiejś liczby rzeczywistej $\alpha$. Teraz dla każdego$n$ formularza $2^{2^k}$, $k \geq 1$, zmień cyfry $\alpha$ w pozycjach $n, n+1, \ldots, 3n$ do $0$„s. Wynikowa liczba$\beta$ najwyraźniej zachowuje właściwość, którą $n$cyfra nie jest obliczalna w $O(n)$ czas, ale ma nieskończenie wiele bardzo dobrych przybliżeń racjonalnych, powiedzmy na zamówienie $O(q^{-3})$, w formie $p/q$. Następnie według twierdzenia Rotha$\beta$nie może być algebraiczne. (To nie jest racjonalne, ponieważ ma arbitralnie długie bloki$0$po obu stronach wyrusza nonzeros.)

Mówiąc bardziej ogólnie, dla dowolnej stałej $k\ge1$, istnieją liczby transcendentalne obliczalne w czasie wielomianowym, ale nie w czasie $O(n^k)$.

Po pierwsze, według twierdzenia o hierarchii czasu istnieje język $L_0\in\mathrm E$ nie do obliczenia w czasie $O(2^{kn})$. Możemy założyć$L\subseteq\{0,1\}^*$, i możemy również założyć, że wszystkie łańcuchy $w\in L$ mają długość podzielną przez $3$.

Po drugie, pozwól $L_1$ być jedyną wersją $L_0$. Dla pewności, dla każdego$w\in\{0,1\}^*$, pozwolić $N(w)$ oznacza liczbę całkowitą, której reprezentacją binarną jest $1w$, i umieścić $L_1=\{a^{N(w)}:w\in L_0\}$. Następnie$L_1\in\mathrm P$, ale $L_1$ nie jest obliczalny w czasie $O(n^k)$. Co więcej,$L_1$ ma następującą właściwość: dla dowolnej $m$, $L_1$ nie zawiera żadnych $a^n$ takie, że $2^{3m+1}\le n<2^{3m+3}$.

Po trzecie, pozwól

$$\alpha=\sum\{2^{-n}:a^n\in L_1\}.$$ (Zakładam tutaj, że pytanie dotyczy obliczania liczb w systemie binarnym. Jeśli nie, to $2$ powyżej można zastąpić dowolną pożądaną bazą, nie ma to znaczenia).

Następnie $\alpha$ jest obliczalny w czasie wielomianowym, ponieważ możemy obliczyć jego pierwszy $n$ bitów, sprawdzając, czy $a,a^2,\dots,a^n$ są w $L_1$. Z tego samego powodu nie można go obliczyć w czasie$O(n^k)$, jak $n$-ty bit określa, czy $a^n\in L_1$.

Dla każdego $m$, pozwolić

$$p=\sum\{2^{2^{3m+1}-n}:n\in L_1,n<2^{3m+1}\}=\lfloor\alpha2^{2^{3m+1}}\rfloor,$$ i $q=2^{2^{3m+1}}$. Następnie $$\left|\alpha-\frac pq\right|\le2^{-2^{3m+3}}=q^{-4}.$$ A zatem, $\alpha$ ma przynajmniej miarę irracjonalności $4$dlatego jest transcendentalny według twierdzenia Rotha .