Setiap angka transendental yang dapat dihitung yang dapat dihitung dalam waktu P tetapi bukan

Apakah ada yang dikenal sejumlah transendental dihitung seperti itu yang $n$ digit th adalah dihitung dalam waktu polinomial, tapi tidak di $O(n)$ ?

Ini adalah konstruksi dari nomor tersebut. Anda dapat berdebat apakah ini berarti nomor seperti itu "diketahui".

Ambil fungsi dari N hingga { 1 , 2 , … , 8 } di mana digit ke - n tidak dapat dihitung dalam waktu O ( n ) . Fungsi semacam itu ada, misalnya, dengan teknik diagonalisasi biasa. Menafsirkan f ( n ) sebagai angka desimal ke - n dari beberapa bilangan real α . Sekarang, untuk setiap n dari bentuk 2 2 k , k ≥ 1 , ubah digit $f$$\mathbb{N}$$\{ 1, 2, \ldots, 8 \}$$n$$O(n)$$f(n)$$n$$\alpha$$n$$2^{2^k}$$k \geq 1$$\alpha$di posisi hingga 0 's. Angka yang dihasilkan β jelas mempertahankan properti bahwa digit ke - n tidak dapat dihitung dalam waktu O ( n ) , tetapi memiliki tak terhingga banyaknya perkiraan yang sangat baik oleh rasional, katakanlah untuk memesan O ( q - 3 ) , dalam bentuk p / q . Maka oleh teorema Roth β tidak bisa aljabar. (Ini tidak rasional karena memiliki blok 0 yang sewenang-wenang$n, n+1, \ldots, 3n$$0$$\beta$$n$$O(n)$$O(q^{-3})$$p/q$$\beta$$0$Dimatikan oleh nonzeros di kedua sisi.)

Lebih umum, untuk setiap konstan , ada nomor transendental dihitung dalam waktu polinomial, tetapi tidak dalam waktu O ( n k ) .$k\ge1$$O(n^k)$

Pertama, berdasarkan teorema hierarki waktu, ada bahasa tidak dapat dihitung dalam waktu O ( 2 k n ) . Kita dapat mengasumsikan L ⊆ { 0 , 1 } ∗ , dan kami juga dapat mengasumsikan bahwa semua string w ∈ L memiliki panjang dibagi 3 .$L_0\in\mathrm E$$O(2^{kn})$$L\subseteq\{0,1\}^*$$w\in L$$3$

Kedua, biarkan menjadi versi unary L 0 . Untuk kepastian, untuk setiap w ∈ { 0 , 1 } ∗ , misalkan N ( w ) menunjukkan bilangan bulat yang representasi binernya adalah 1 w , dan beri L 1 = { a N ( w ) : w ∈ L 0 } . Kemudian L 1 ∈ P , tetapi L 1 tidak dapat dihitung dalam waktu $L_1$$L_0$$w\in\{0,1\}^*$$N(w)$$1w$$L_1=\{a^{N(w)}:w\in L_0\}$$L_1\in\mathrm P$$L_1$ . Selain itu, L 1 memiliki properti berikut: untuk setiap m , L 1 tidak mengandung suatu n sehingga 2 3 m + 1 ≤ n < 2 3 m + 3 .$O(n^k)$$L_1$$m$$L_1$$a^n$$2^{3m+1}\le n<2^{3m+3}$

Ketiga, mari (Saya berasumsi di sini bahwa pertanyaannya adalah tentang menghitung angka dalam biner. Jika tidak, 2 di atas dapat diganti dengan basis yang diinginkan, itu tidak masalah.)

$$\alpha=\sum\{2^{-n}:a^n\in L_1\}.$$ $2$

Kemudian dapat dihitung dalam waktu polinomial, karena kita dapat menghitung bit n pertamanya dengan memeriksa apakah a , a 2 , … , a n berada di L 1 . Untuk alasan yang sama, tidak dihitung dalam waktu O ( n k ) , sebagai n bit th menentukan apakah suatu n ∈ L 1 .$\alpha$$n$$a,a^2,\dots,a^n$$L_1$$O(n^k)$$n$$a^n\in L_1$

Untuk setiap , biarkan p = Σ { 2 2 3 m + 1 - n : n ∈ L 1 , n < 2 3 m + 1 } = ⌊ a 2 2 3 m + 1 ⌋ , dan q = 2 2 3 m + 1 . Lalu | α - $m$

$$p=\sum\{2^{2^{3m+1}-n}:n\in L_1,n<2^{3m+1}\}=\lfloor\alpha2^{2^{3m+1}}\rfloor,$$ $q=2^{2^{3m+1}}$ Jadi,αmemiliki ukuran irasionalitas setidaknya4, oleh karena itu transendental olehteorema Roth. $$\left|\alpha-\frac pq\right|\le2^{-2^{3m+3}}=q^{-4}.$$ $\alpha$$4$