Konstruktiv effiziente Algorithmen ohne effiziente Korrektheit und Effizienznachweis

17

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

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

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.

Kaveh
quelle
1
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
2
Wie wäre es mit einer Polynomialzeit-Primalitätsprüfung? Dieser Beweis ist wahrscheinlich so kompliziert, dass es schwierig ist, in zu stecken . S21
Andrej Bauer
4
@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 S 1 2 ist . Ich denke, es könnte einfacher sein, mit T V 0 und S 1 2 am deterministischen Polyzeit-Fall festzuhalten . TV0S21TV0S21
Kaveh
1
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
4
@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:

14

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 Σ b 1 -Property , die definiert Primzahlen im Standardmodell und S 1 2¬ P ( x ) ( y 1 , y 2 ) ( 1 < y 1 , y 2 < x x = y 1, y 2 )P(x)Σ1b

S21¬P(x)(y1,y2)(1<y1,y2<xx=y1y2)
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 S 1 2 ). 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.Σ1bS21
François G. Dorais
quelle
10

TC0VTC0

TV0VTC0TC0

(an)

p(ap)=1ap

S21

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
9

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
2
S21
2
S21S21
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
2
@Francois, warum nicht eine Antwort posten? :)
Kaveh
8
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