Jede berechenbare transzendentale Zahl, die in P-Zeit berechenbar ist, jedoch nicht

Gibt es eine bekannte berechenbare transzendentale Zahl, so dass ihre te Ziffer in Polynomzeit berechenbar ist, aber nicht in ?O ( n $n$$O(n)$

Hier ist der Aufbau einer solchen Zahl. Sie können argumentieren, ob dies bedeutet, dass eine solche Nummer "bekannt" ist.

Nehmen Sie eine beliebige Funktion von N bis { 1 , 2 , … , 8 }, wobei die n -te Ziffer in O ( n ) -Zeit nicht berechenbar ist . Eine solche Funktion besteht beispielsweise durch die übliche Diagonalisierungstechnik. Interpretiere f ( n ) als die n -te Dezimalstelle einer reellen Zahl α . Ändern Sie nun für jedes n der Form 2 2 k , k ≥ 1 die Ziffern von $f$$\mathbb{N}$$\{ 1, 2, \ldots, 8 \}$$n$$O(n)$$f(n)$$n$$\alpha$$n$$2^{2^k}$$k \geq 1$$\alpha$in den Positionen bis 0 . Die resultierende Zahl β behält offensichtlich die Eigenschaft bei, dass die n -te Ziffer nicht in O ( n ) -Zeit berechenbar ist , sondern unendlich viele sehr gute Annäherungen durch Rationalitäten, etwa zur Ordnung O ( q - 3 ) , der Form p / q aufweist . Dann kann nach Roths Theorem β nicht algebraisch sein. (Es ist nicht rational, weil es beliebig lange Blöcke von $n, n+1, \ldots, 3n$$0$$\beta$$n$$O(n)$$O(q^{-3})$$p/q$$\beta$$0$wird auf beiden Seiten von ungleich Null abgesetzt.)

Allgemeiner gibt es für jede Konstante transzendentale Zahlen, die in der Polynomzeit berechnet werden können, jedoch nicht in der Zeit O ( n k ) .$k\ge1$$O(n^k)$

Erstens existiert nach dem Zeithierarchiesatz eine Sprache , die in der Zeit O ( 2 k n ) nicht berechenbar ist . Wir können L ⊆ { 0 , 1 } ∗ annehmen, und wir können auch annehmen, dass alle Strings w ∈ L eine durch 3 teilbare Länge haben .$L_0\in\mathrm E$$O(2^{kn})$$L\subseteq\{0,1\}^*$$w\in L$$3$

Zweitens sei die unäre Version von L 0 . Für Bestimmtheit, für jede w ∈ { 0 , 1 } * sei N ( W ) bezeichnen die ganze Zahl , deren binäre Darstellung ist 1 w und legte L 1 = { a N ( w ) : w ∈ L 0 } . Dann ist L 1 ∈ P , aber L 1 ist in der Zeit O nicht berechenbar$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$ . Außerdem L 1 hat die folgende Eigenschaft: Für jeden m , L 1 enthält keine a n , so dass 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}$

Drittens sei (Ich gehe hier davon aus, dass es um die Berechnung von Zahlen in Binärform geht. Wenn nicht, kann die obige 2 durch eine beliebige Basis ersetzt werden, das spielt keine Rolle.)

Dann ist in Polynomzeit berechenbar, da wir seine ersten n Bits berechnen können, indem wir prüfen, ob a , a 2 , … , a n in L 1 sind . Aus dem gleichen Grund ist es in der Zeit O ( n k ) nicht berechenbar , da das n- te Bit bestimmt, ob a n ∈ L 1 ist .$\alpha$$n$$a,a^2,\dots,a^n$$L_1$$O(n^k)$$n$$a^n\in L_1$

Für jeden , läßt p = Σ { 2 2 3 m + 1 - n : n ∈ L 1 , n < 2 3 m + 1 } = ⌊ & agr; 2 2 3 m + 1 ⌋ , und q = 2 2 3 m + 1 . Dann | α - $m$