Konstruktiv effiziente Algorithmen ohne effiziente Korrektheit und Effizienznachweis

Ich suche nach natürlichen Beispielen für effiziente Algorithmen (dh in Polynomialzeit) st

ihre Richtigkeit und Wirksamkeit kann konstruktiv nachgewiesen werden (zB in $PRA$ oder $HA$ ), aber
Es ist kein Beweis bekannt, bei dem nur effiziente Konzepte verwendet werden (dh wir wissen nicht, wie ihre Richtigkeit und Effizienz in oder ). $TV^0$ $S^1_2$

Ich kann selbst künstliche Beispiele machen. Ich möchte jedoch interessante natürliche Beispiele, dh Algorithmen, die für sich selbst studiert und nicht nur zur Beantwortung dieser Art von Fragen entwickelt wurden.

cc.complexity-theory reference-request lo.logic proof-complexity constructive-mathematics Kaveh
quelle

Vielleicht etwas aus der Automatentheorie, wo ein Algorithmus einfach ist, aber um zu zeigen, dass er funktioniert, muss man alle Teilmengen von irgendetwas berücksichtigen?

Andrej Bauer

Wie wäre es mit einer Polynomialzeit-Primalitätsprüfung? Dieser Beweis ist wahrscheinlich so kompliziert, dass es schwierig ist, in

zu stecken .

S_{2}^{1}

$S^1_2$

Andrej Bauer

@Neel, eigentlich Emils These " Schwaches Pigeonhole-Prinzip und randomisierte Berechnung ", beschäftigt sich mit der Formalisierung probabilistischer Algorithmen. Ein Hauptaxiom, das für die Formalisierung einiger davon benötigt wird, scheint die ungefähre Zählung zu sein, die nicht Teil von

oder

. Ich denke, es könnte einfacher sein, mit

und

am deterministischen Polyzeit-Fall festzuhalten .

T V^{0}

$TV^0$

S_{2}^{1}

$S^1_2$

T V^{0}

$TV^0$

S_{2}^{1}

$S^1_2$

Kaveh

ps: Es wäre interessanter, wenn wir nachweisen könnten, dass die Richtigkeit / Effizienz der Algorithmen in diesen Theorien nicht nachweisbar ist oder zumindest Aussagen entspricht, von denen angenommen wird, dass sie in ihnen nicht beweisbar sind. Allerdings ist es bei dem, was wir derzeit wissen, wahrscheinlich zu viel verlangt.

Kaveh

@Neel, der größte Teil der relevanten Wahrscheinlichkeit kann in Systemen erster Ordnung durchgeführt werden, da Sie die genaue Wahrscheinlichkeit eines Ereignisses nie wirklich kennen müssen. In der Regel müssen Sie diese Wahrscheinlichkeit nur mit bestimmten rationalen Zahlen vergleichen.

François G. Dorais

Antworten:

Dies ist die gleiche Idee wie die Antwort von Andrej, aber mit mehr Details.

[Krajicek und Pudlak 960 LNCS 1995, pp. 210-220 ] haben gezeigt , dass , wenn ist ein -Property , die definiert Primzahlen im Standardmodell und $P(x)$ $\Sigma^b_1$

S_{2}^{1} ⊢ \neg P (x) \to (\exists y_{1}, y_{2}) (1 < y_{1}, y_{2} < x \land x = y_{1} y_{2})

$S^1_2 \vdash \lnot P(x) \to (\exists y_1,y_2)(1 < y_1, y_2 < x \land x = y_1y_2)$ dann gibt es einen polynomiellen Zeitfaktor-Algorithmus. Dies gibt eine Reihe von Beispielen, da jeder NP-Algorithmus für Primalitätstests im Grunde genommen eine solche

-Formel ergibt. Insbesondere der AKS-Primalitätstest liefert eine solche Formel (bei entsprechender Neufassung in der Sprache von

). Die Arbeit von Krajicek und Pudlak enthält weitere Beispiele für diese Art der Kryptografie, datiert jedoch einige Jahre vor AKS und den damit verbundenen Fortschritten.

Σ_{1}^{b}

$\Sigma^b_1$

S_{2}^{1}

$S^1_2$

François G. Dorais
quelle

$\mathrm{TC}^0$ $\mathit{VTC}^0$

$\mathit{TV}^0$ $\mathit{VTC}^0$ $\mathrm{TC}^0$

$\left(\frac an\right)$

$p$ $\left(\frac ap\right)=1$ $a$ $p$

$S^1_2$

Eine weitere Klasse von Beispielen sind Irreduzibilitätstests und Faktorisierungsalgorithmen für Polynome (hauptsächlich über endliche Felder und über die Rationen). Diese stützen sich ausnahmslos auf den kleinen Satz von Fermat oder seine Verallgemeinerungen (unter anderem) und sind daher nicht als formalisierbar in einer geeigneten Theorie der beschränkten Arithmetik bekannt. Typischerweise sind diese Algorithmen randomisiert, aber für deterministische Polynomzeitbeispiele kann man Rabins Irreduzibilitätstest oder den Tonelli-Shanks-Quadratwurzel-Algorithmus (so formuliert, dass ein quadratischer Nichtrest als Teil der Eingabe erforderlich ist) verwenden.

Emil Jeřábek unterstützt Monica
quelle

Der AKS-Primalitätstest scheint ein guter Kandidat zu sein, wenn man Wikipedia glauben will.

Ich würde jedoch erwarten, dass ein solches Beispiel schwer zu finden ist. Bestehende Beweise werden so formuliert, dass sie offensichtlich nicht in beschränkter Arithmetik ausgeführt werden, aber sie werden wahrscheinlich mit mehr oder weniger Aufwand (normalerweise mehr) auf begrenzte Arithmetik "anpassbar" sein.

Andrej Bauer
quelle

S_{2}^{1}

$S^1_2$

S_{2}^{1}

$S^1_2$

S_{2}^{1}

$S^1_2$

Es gibt eine wunderbare Arbeit von Krajicek und Pudlak, die ein paar weitere Beispiele gibt: karlin.mff.cuni.cz/~krajicek/j-crypto.ps

François G. Dorais

@Francois, warum nicht eine Antwort posten? :)

Kaveh

Daher bekomme ich die höchste Anzahl von Upvotes, wenn ich früh Glück habe, während andere tatsächlich wissen, was los ist. Mathe ist wie MTV.

Andrej Bauer