Randomisierter Algorithmus, der deterministisch "aussieht"?

Gibt es ein interessantes Beispiel für einen randomisierten Algorithmus für ein Suchproblem , der unabhängig von seiner internen Zufälligkeit immer dieselbe (richtige) Antwort ausgibt, die Zufälligkeit jedoch ausnutzt, sodass seine erwartete Laufzeit besser ist als die Laufzeit der schnellsten bekannten deterministischer Algorithmus für das Problem?

Insbesondere habe ich mich gefragt, ob es einen solchen Algorithmus gibt, um eine Primzahl zwischen n und 2n zu finden. Es ist kein polynomieller zeitdeterministischer Algorithmus bekannt. Es gibt einen trivialen randomisierten Algorithmus, bei dem nur zufällige Ganzzahlen im Intervall abgetastet werden, was dank des Primzahlsatzes funktioniert . Aber gibt es einen Algorithmus der oben genannten Art, dessen erwartete Laufzeit zwischen beiden liegt?

BEARBEITEN: Um meine Frage ein wenig zu verfeinern, wollte ich einen solchen Algorithmus für ein Problem, bei dem es viele mögliche korrekte Ausgaben gibt, und dennoch setzt der randomisierte Algorithmus unabhängig von seiner Zufälligkeit auf einen. Mir ist klar, dass die Frage wahrscheinlich nicht vollständig spezifiziert ist ...

Shafi Goldwasser teilte mir mit, dass sie und die Mitautoren genau solche Algorithmen für zahlentheoretische Probleme untersucht haben! Folgendes ist bekannt:

1. Lenstra hat gezeigt, dass es einen solchen Algorithmus gibt, um eine quadratische nicht-restliche Modifikation einer gegebenen Primzahl zu finden.

2. $\mathbb{Z}_p^*$$p$$2q + 1$$q$

$n$$2n$

$n$$2n$

Zählen randomisierte Datenstrukturen?

Es gibt die Überspringliste, die eine sortierte assoziative Kartendatenstruktur ist.

$O(\log n)$

Wie wäre es mit Kelners und Spielmans randomisiertem Polynom-Zeit-Simplex-Algorithmus? Es findet den optimalen Eckpunkt eines linearen Programms. Es ist kein deterministischer Simplex-Algorithmus bekannt, der nachweislich in polynomieller Zeit abläuft, und für viele von ihnen können pathologische Instanzen konstruiert werden, bei denen der Algorithmus exponentielle Zeit benötigt.

Natürlich gibt es Interieur-Punkt-Algorithmen für die Polynomzeit, also ist es nicht genau das, wonach Sie suchen.

$2^n$$n$$2^n$

$2^{n-1}$

Qualifiziert sich das?

$\mathbb{F}_p$$\log p$$p$

$\log p$

Es gab ein Polymath-Projekt, das sich mit einer verwandten Frage befasste: http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Bei Ihrer ersten Frage habe ich zuerst an Quicksort gedacht, aber das sollte offensichtlich sein.

Es gibt einen String-Matching-Algorithmus ( Nebel, 2006 ), der probabilistische Ideen verwendet. Ich weiß jedoch, ob dies der schnellste existierende Ansatz ist und Sie anscheinend einige Beispiele für das Training benötigen.

Das folgende STACS '97-Dokument könnte für Ihren Fall interessant sein: Die Komplexität der Generierung von Testinstanzen .

Abstract: Vor kurzem hat Watanabe ein neues Framework zum Testen der Korrektheit und des durchschnittlichen Fallverhaltens von Algorithmen vorgeschlagen, die vorgeben, ein bestimmtes NP-Suchproblem im Durchschnitt effizient zu lösen. Die Idee ist, zertifizierte Instanzen zufällig so zu generieren, dass sie der zugrunde liegenden Distribution ähneln. Wir diskutieren diesen Ansatz und zeigen, dass Testinstanzen für jedes NP-Suchproblem mit nicht adaptiven Abfragen an ein NP-Orakel generiert werden können. Außerdem stellen wir Generatoren für Las Vegas- und Monte-Carlo-Testinstanzen vor und zeigen, dass mit diesen Generatoren herausgefunden werden kann, ob ein Algorithmus im Durchschnitt korrekt und effizient ist. Tatsächlich ist es nicht schwer, Monte-Carlo-Generatoren für alle RP-Suchprobleme sowie Las Vegas-Generatoren für alle ZPP-Suchprobleme zu konstruieren. Auf der anderen Seite,

Sehen Sie sich insbesondere Seite 384 unter Folgerung 12 an:

$\rm{ZPP}$$\rm{RP}$$\rm{ZPP}$$\rm{NP}$$\rm{NP} \cap \rm{coNP}$

Vor [AKS] hatte Primality coRP- und RP-Algorithmen (Miller-Rabin für coRP, Adleman-Huang für RP). Eine natürliche Nullfehlererweiterung wäre, beide gleichzeitig auszuführen, bis Sie den Fehler auf reduzieren$\frac{1}{n^c}$$\text{polylog}(n)$