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

9

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

XL _At_Here_There
quelle
2
Es macht immer noch keinen Sinn. Meinst du "... aber nicht rechtzeitig " oder was? Ö(n)
Emil Jeřábek
Ich meine in P-Zeit und nicht in . Ich bin mir nicht sicher, ob mein Englisch falsch ist oder deins. Trotzdem danke ich Ihnen für Ihren Kommentar. Ö(n)
XL _At_Here_There
2
Wenn es dem Autor gelingt, diese Frage in lesbarem Englisch zu formulieren, könnte dies mit der Hartmanis-Stearns-Vermutung zusammenhängen: Jede reelle Zahl, die von einer Echtzeit-Multitape-Turing-Maschine berechnet wird, ist entweder transzendent oder rational.
Gamow
@Gamow rechts , aber es schließt den Fall der Hartmanis-Stearns-Vermutung aus.
XL _At_Here_There
2
Ich habe versucht, dies verständlich zu machen, aber es ist immer noch nicht sehr klar. Meinen Sie nicht bekannt, dass es in berechenbar oder nachweislich nicht in O ( n ) berechenbar ist ? Was ist das Berechnungsmodell: Einzel- oder Multitape-Turing-Maschine oder etwas anderes? Ö(n)Ö(n)
Sasho Nikolov

Antworten:

19

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 αfN.{1,2,,8}}nÖ(n)f(n)nαn22kk1α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 0 hatn,n+1,,3n0βnÖ(n)O(q3)p/qβ0wird auf beiden Seiten von ungleich Null abgesetzt.)

Jeffrey Shallit
quelle
12

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 ) .k1O(nk)

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 .L0EO(2kn)L{0,1}wL3

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 1P , aber L 1 ist in der Zeit O nicht berechenbarL1L0w{0,1}N(w)1wL1={aN(w):wL0}L1PL1 . Außerdem L 1 hat die folgende Eigenschaft: Für jeden m , L 1 enthält keine a n , so dass 2 3 m + 1n < 2 3 m + 3 .O(nk)L1mL1an23m+1n<23m+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.)

α={2n:anL1}.
2

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 nL 1 ist .αnein,ein2,,einnL.1Ö(nk)neinnL.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 | α - pm

p={223m+1- -n::nL.1,n<23m+1}}=α223m+1,
q=223m+1 Somit hatαein Irrationalitätsmaß von mindestens4, daher ist es nachRoths Theoremtranszendent.
|α- -pq|2- -23m+3=q- -4.
α4
Emil Jeřábek
quelle
2
Hmm, ich sehe, dass ich geschöpft wurde. Ich werde die Antwort trotzdem hinterlassen, da sie für jemanden nützlich sein kann.
Emil Jeřábek
3
Ich habe Jeffreys Beitrag als Antwort auf die Frage gewählt, da seine Antwort früher veröffentlicht wurde.
XL _At_Here_There
6
Ja. Ich werde mich das nächste Mal daran erinnern, keine Zeit und Mühe damit zu verschwenden, eine gründliche Antwort mit allen technischen Details zu schreiben, da es anscheinend wertvoller ist, stattdessen ein paar Minuten früher zu posten.
Emil Jeřábek
3
: D, großartig! Ich hoffe, wir können mehr Themen genießen.
XL _At_Here_There