Welche konkreten Hinweise gibt es für P = RP?

RP ist die Klasse von Problemen, die von einer nichtdeterministischen Turing-Maschine entschieden werden können, die in Polynomzeit endet, aber auch einseitige Fehler zulässt. P ist die übliche Klasse von Problemen, die von einer deterministischen Turing-Maschine entschieden werden kann, die in der Polynomzeit endet.

P = RP ergibt sich aus einer Beziehung in der Schaltungskomplexität. Impagliazzo und Wigderson zeigten, dass P = BPP folgt, wenn für ein Problem, das in der deterministischen Exponentialzeit entschieden werden kann, auch Schaltkreise mit Exponentialgröße erforderlich sind (beachten Sie, dass P = BPP P = RP impliziert). Vielleicht scheint es aufgrund dieser Ergebnisse unter einigen Komplexitätstheoretikern das Gefühl zu geben, dass probabilistische Reduktionen wahrscheinlich derandomisiert werden können.

Welche anderen spezifischen Beweise gibt es für P = RP?

Die Existenz von Problemen in DTIME (2 ^ O (n)), für deren Berechnung Schaltkreise mit Exponentialgröße erforderlich sind (dies ist die Annahme in IW), erscheint plausibel, da wir sonst eine Ungleichmäßigkeit hätten, die JEDES Rechenproblem beschleunigt - welches Das widerspricht völlig dem gegenwärtigen Denken, das für "normale" Probleme keine "zu signifikante" Lücke zwischen einheitlicher und uneinheitlicher Komplexität sieht. Diese Überlegung beruht auf der Tatsache, dass es nur sehr wenige Beispiele gibt, bei denen ein "uneinheitlicher" Algorithmus bekannt ist, der signifikant besser ist als der bekannte einheitliche (wiederum mit Ausnahme der Derandomisierung).

Ein weiterer "Beweis" ist, dass wir im Verhältnis zu einem zufälligen Orakel P = BPP haben.

Jedes konkrete Ergebnis der Derandomisierung zeigt, dass P = BPP ist. Als solches ist PRIMES in P (Agrawal-Kayal-Saxena'02) ein gutes Beispiel. Im Allgemeinen gibt es bei BPP nur wenige natürliche Probleme, von denen nicht bekannt ist, dass sie bei P auftreten (Polynomial Identity Testing ist eine bemerkenswerte Ausnahme).

Ähnlich wie das erwähnte Ergebnis hat Hastad-Impagliazzo-Levin-Luby '99 gezeigt, dass die Existenz von Einwegfunktionen die Existenz von Pseudozufallsgeneratoren impliziert. Dies impliziert zwar nicht direkt P = BPP basierend auf der Existenz von Einwegfunktionen, zeigt jedoch, dass Pseudozufallsgeneratoren von minimalen kryptographischen Annahmen ausgehen. Dies kann als ein weiterer Hinweis darauf gesehen werden, dass BPP nicht leistungsfähiger ist als P.

$P^X=RP^X$ $X$$ZPP=RP=EXP$$P$

Das Obige spricht natürlich von der Derandomisierung randomisierter Polynom-Zeit-Turing-Reduktionen anstatt der üblichen Polynom-Zeit-Viel-Eins-Reduktionen. Es würde mich nicht wundern, wenn Hellers Orakel angepasst werden kann, um eine Menge X so zu geben, dass Y für alle Y exponentiell um ein Vielfaches auf X reduzierbar ist, wenn Y auf X RP-reduzierbar ist, aber ohne die Konstruktion I zu durchlaufen konnte es nicht schwören.

$USAT_Q$$Q = \bot$$USAT_{\bot}$

$\phi$$\phi$$\phi$$k$$x$$\phi$$k$$x$$k$$x$$k$

$k$$k$$n$$USAT_{\bot}$$n$

$\epsilon > 0$$n^{1-\epsilon}$