Der Trick zum Beweis der doppelt exponentiellen Komplexität der Presburger-Arithmetik

Ich habe dies auf MathUnderflow gepostet, aber keine Antworten erhalten. Ich dachte, ich würde es hier versuchen.

Ich lese die alte Arbeit von Rabin und Fischer [wird nach Möglichkeit einen Link veröffentlichen], wo unter anderem die doppelt exponentielle Komplexität der Presburger-Arithmetik bewiesen wird.

Der Beweis beruht auf der Existenz einer Formel informell " " mit behauptet . Obwohl die Konstruktion dieser Formel in der Arbeit nicht angegeben ist, war es für mich eine Überraschung, da sie angesichts dieser Bindung und der Tatsache, dass wir nur über Addition verfügen, vermutlich höchst nicht trivial ist! ¹$I_{n}(x)$$x < 2^{2^{kx+1}}$$|I_{n}| \in O(n)$

Ich habe später erfahren, dass die Konstruktion dieser Formel auf einem "Trick" beruht, der zuvor von Fischer und unabhängig von Volker Strassen entdeckt wurde, aber ich habe es nicht geschafft, ein Papier aufzuspüren, das diesen Trick im Detail beschreibt!

Wenn also jemand etwas über das Papier weiß, über das ich spreche, und mich entweder in seine Richtung weisen oder mir sogar den Trick beschreiben kann ...

Dieser Beitrag aus Liptons Blog enthält einen Link zum Artikel sowie Erwähnungen [und liefert eine grobe, für mich leider unzureichende Skizze] des genannten Tricks, übrigens.

¹ Ich weiß, dass dies eine vage Beschreibung ist. Eine ausreichend detaillierte Beschreibung wäre jedoch viel zu lang für einen SX-Beitrag, daher hoffe ich nur, dass jemand, der bereits über das betreffende Papier Bescheid weiß und daher mit dieser kurzen Skizze auskommen kann, darauf stößt und mir helfen kann .

Martins Kommentar (und Yuvals Follow-up) enthält die Referenz, die die Konstruktion ausführlich erklärt.

Ich werde ein wenig näher darauf eingehen, weil ich denke, dass es ein großartiger Beweis ist: Im Grunde genommen führt es den "üblichen" Beweis der Unentscheidbarkeit von PA durch (Arithmetik mit Addition und Multiplikation), aber relativiert auf$2^{2^{c\cdot n}}$ ! Das heißt, es gibt eine (kurze) Formel, die die Multiplikation bis zu dieser Zahl ausdrückt, dh eine Formel so dass $M_n(x,y,z)$

$$M_n(x,y,z) \Leftrightarrow x\times y=z\ \wedge x< 2^{2^n}$$

Jetzt bauen Sie durch Induktion auf , mit einem entscheidenden Trick, der an den Karatsuba-Algorithmus zum Multiplizieren von Binärzahlen oder bestimmte Tricks für die Matrixmultiplikation erinnert:$M_n$$n$

In der Definition für Sie eine Konjunktion der Form $M_{n+1}(x,y,z)$

$$M_{n}(x_1,y_1,z_1)\wedge M_{n}(x_2,y_2,z_2)\wedge M_{n}(x_3,y_3,z_3)$$

Sie können dies jedoch durch ersetzen

$$\forall u v w,(u=x_1\wedge v=y_1\wedge w=z_1)\vee(u=x_2\wedge v=y_2\wedge w=z_2)\vee(u=x_3\wedge v=y_3\wedge w=z_3)\Rightarrow M_n(u,v,w)$$

Dieser Trick ermöglicht eine lineare Vergrößerung anstelle einer exponentiellen (als Funktion von ).$n$

Es gibt noch ein paar andere Tricks, aber dies ist der wichtigste. Die Interna der Rekursion sind natürlich wichtig, aber die Ähnlichkeit mit dem Karatsuba-Trick ist wirklich bemerkenswert.