Rechenkomplexität von pi

31

Lassen

L = { n : die  n t h  Binärziffer von  π  ist  1 }L = { n : das  nt h Binärziffer von  π ist  1 }

(wobei n als binär codiert angesehen wird). Was können wir dann über die rechnerische Komplexität von L sagen ? Es ist klar , dass L E X P . Und wenn ich mich nicht irre, die erstaunlich „BBP-Typ“ Algorithmen zur Berechnung der n t h Bit von π mit quasilinearen Zeit und ( log n ) O ( 1 ) Speicher, ohne dass die vorherige Bits, die Ausbeute berechnen L P S P A C E .nL

Können wir es noch besser machen und L (sagen wir) in der Zählhierarchie platzieren? In der anderen Richtung ergibt sich für L überhaupt eine Härte (auch eine extrem schwache wie T C 0 -Härte)?

Eine interessante verwandte Sprache ist

L ' = { x , t : x  tritt als Teilkette innerhalb der ersten  t  Ziffern  π }

(wobei wiederum t binär geschrieben ist). Wir haben

L 'N P L

und daher L 'P S P A C E ; Es würde mich sehr interessieren, wenn etwas Besseres bekannt ist.

Scott Aaronson
quelle
9
(1) Weil π die berühmteste transzendentale Zahl ist und viel darüber bekannt ist. (2) Weil ich ein konkretes Beispiel wollte. (Ich würde mich natürlich auch sehr für die analogen Fragen zu e , interessieren2 , usw., zu welchem Ausmaß auch immer die Antworten unterscheiden) (3) Da für Chaitins.Ω, ich die Antwort schon wissennämlichBerechnung dern t h Binärziffer ist unberechenbare! (Und ichvermute,es ist möglich, eine Reduktion zu geben, die zeigt, dass das Subsequenzsuchproblem auch fürΩ nichtberechenbar ist... jemand sieht wie?)
Scott Aaronson
6
@ScottAaronson, ich denke , wir können alle Strings iterieren x Länge t und fragen , ob x , t ist in der Sprache; dies gibt uns alle ersten t Bits von Ω .
USUL
3
Ich habe eine ähnliche "Zahlentheorie" -Sprache: L = { n  das zweite untere Bit der  n- ten Primzahl ist  1 } :-)
Marzio De Biasi
3
Durch die Art und Weise, geprüft I Weihrauch, am Ende von Abschnitt 7.2 heißt es , dass n-te Bit von trigonometrischen Funktionen und ihre Inversen in der Zeit berechnet werden , t m ( n ) lg n unter Verwendung der signierte -stellige Darstellung (erlaubt - 1 in Neben 0 und 1 als Ziffer) auf kompakten Teilmengen ihrer Domain. ( t m ist die Komplexität der binären ganzzahligen Multiplikation.)
Kaveh

Antworten:

26

OK, James Lee hat mich auf diesen Artikel von Samir Datta und Rameshwar Pratap aus dem Jahr 2011 hingewiesen , der beweist, dass meine Sprache L (die die Ziffern von π codiert ) in der vierten Ebene der Zählhierarchie liegt ( P H P P P P P P ; danke an SamiD unten für den Hinweis auf ein fehlendes P P in der Zeitung, das ich in meiner Antwort einfach wiederholt habe!). Das Papier diskutiert auch explizit meine Frage der unteren Schranken der Komplexität der Berechnung der Binärziffern irrationaler Zahlen, obwohl es nur gelingt, eine sehr schwache untere Schranke für die Berechnung der Binärziffern rationaler Zahlen zu beweisenzahlen. Genau das habe ich gesucht.

Update (3. April): Eine amüsante Folge davon, dass die Ziffern von π in der Zählhierarchie berechenbar sind, ist wie folgt. Angenommen, π ist eine normale Zahl (deren binäre Expansion schnell zu "effektiv zufällig" konvergiert), und angenommen, dass P = P P (wobei die Simulation nur einen kleinen Polynom-Overhead beinhaltet). Dann wäre es denkbar, Ihren Computer so zu programmieren, dass er beispielsweise das erste Auftreten der vollständigen Werke von Shakespeare in der binären Erweiterung von π findet . Wenn das absurd für Sie klingt, dann vielleicht sollte es als zusätzliche Hinweise darauf , dass getroffen werden PP P . :-)

Scott Aaronson
quelle
OK, aber es heißt, ich muss 5 Stunden warten, bevor ich das tue!
Scott Aaronson
7
BTW erwähnte Papier nur reduziert im wesentlichen das Problem B i t S L P und irrtümlicherweise zitiert die gebunden als P H P P P P . Die beste Schranke bekannt ist zur Zeit P H P P P P P P wie hier gezeigt: eccc.hpi-web.de/report/2013/177
Samid