Kauft uns der Zufall irgendetwas in P?

Sei die Klasse der Entscheidungsprobleme mit einem beschränkten zweiseitigen fehlerzufälligen Algorithmus, der in der Zeit . $\mathsf{BPTIME}(f(n))$ $O(f(n))$

Kennen wir jedes Problem , so dass aber ? Ist ihre Nichtexistenz bewiesen? $Q \in \mathsf{P}$ $Q \in \mathsf{BPTIME}(n^k)$ $Q \not \in \mathsf{DTIME}(n^k)$

Diese Frage wurde auf cs.SE hier gestellt , aber keine zufriedenstellende Antwort erhalten.

cc.complexity-theory ds.algorithms randomized-algorithms derandomization aelguindy
quelle

(1) BPP (f (n)) wird üblicherweise als BPTIME (f (n)) bezeichnet. (2) In Bezug auf die rechnerische Komplexität glaube ich, dass dies offen ist. (Viele Beispiele sind in den Einstellungen für die Abfragekomplexität und die Kommunikationskomplexität bekannt.) (3) Wenn ihre Nichtexistenz bereits bewiesen wäre, würden wir bereits wissen, dass P = BPP.

Tsuyoshi Ito

Übrigens, in der Frage auf cs.stackexchange.com haben Sie ein Missverständnis über die Beziehung zwischen BPTIME und ZPTIME, und das könnte ein Grund dafür sein, dass Sie keine zufriedenstellende Antwort erhalten haben.

Tsuyoshi Ito

@TsuyoshiIto Danke, ich stimme nicht zu, dass ich die Einstellung auf Probleme in

einschränke , wenn wir die Existenz nicht beweisen, dann wissen wir, dass

ist . Vielleicht,

, während

P = B P P

$P=BPP$

P

$P$

B P T I M E (n^{k}) \cap P = D T I M E (n^{k})

$BPTIME(n^k) \cap P = DTIME(n^k)$

Vermisse ich im Allgemeinen etwas? Könnten Sie bitte auch auf mein Missverständnis bezüglich

und

B P T I M E (n^{k}) \neq D T I M E (n^{k})

$BPTIME(n^k) \neq DTIME(n^k)$

B P T I M E

$BPTIME$

Z P T I M E

$ZPTIME$

hinweisen

Ihre Frage besagt nicht, dass Sie das Problem Q auf das Innere von P beschränken. Wenn dies Ihre Absicht ist, bearbeiten Sie die Frage.

Tsuyoshi Ito

Um den 1-Median eines endlichen metrischen Raums mit wenigen Abfragen an die Distanzfunktion zu approximieren, ergibt ein zufälliger Punkt mit guter Wahrscheinlichkeit eine 2-Approximation in Erwartung und eine (2 + eps) -approx. Aber kein deterministischer Algorithmus, der die Distanzfunktion

mal abfragt, kann es besser als eine 4-Approximation. [ Chang 2013 ]

o (n^{2})

$o(n^2)$

Neal Young

Antworten:

Ein weiteres Beispiel ist die Schätzung des Volumens eines Polyeders in hohen Dimensionen. Es gibt eine unbedingte Untergrenze für deterministische Strategien, um das Volumen sogar einem Exponentialfaktor anzunähern, aber es gibt ein FPRAS für das Problem.

Update: das relevante Papier ist (Link zum PDF ):

I. Barany und Z. Furedi. Die Berechnung des Volumens ist schwierig, Discrete and Computational Geometry 2 (1987), 319-326.

Suresh Venkat
quelle

Können Sie eine Referenz für die unbedingte Untergrenze angeben?

T ....

hinzugefügte Referenz.

Suresh Venkat

Problem : Ein Array besteht aus 1s und 0s. Finde ein so, dass 1 ist. $A[1..2n]$ $n$ $n$ $i$ $A[i]$

Sie dürfen abfragen, welche Nummer in . Jede Abfrage benötigt eine konstante Zeit. $A[i]$

Lösung : Randomisierter Algorithmus: Wählen Sie einen zufälligen Index und prüfen Sie, ob $i$ $A[i]$ ist. Die erwartete Anzahl von Abfragen ist 2, aber jeder deterministische Algorithmus muss mindestens Abfragen durchführen. Daher ist die randomisierte Obergrenze in diesem Modell strikt besser als die deterministische Untergrenze. $n$

Dies ist ein Beispiel für die Komplexität von Abfragen, auf die sich Tsuyoshi im Kommentar bezog.

Jagadisch
quelle

Jeder deterministische Algorithmus muss im schlimmsten Fall mindestens

Anfragen stellen .

n

$n$

Argentpepper

Was meinst du mit "derzeit kennen wir keinen nicht-trivialen unteren Beweis für ein Problem in NP (geschweige denn P)"?

Kristoffer Arnsfelt Hansen

Vielleicht habe ich das Wort "nicht trivial" schlampig verwendet. Ich meinte 'Derzeit können wir keine bedingungslose Untergrenze von

für

für SAT oder irgendein Problem in NP beweisen '. Ist das korrekt?

Ω (n^{k})

$\Omega(n^k)$

k > 0

$k>0$

Jagadish

Naja, vielleicht nicht für "nette" Probleme wie SAT; Denken Sie jedoch daran, dass wir solche Untergrenzen für andere Probleme aus den Zeithierarchiesätzen haben. Dabei geht es nicht um "nette" Probleme, sondern um Komplexitätsklassen.

Kristoffer Arnsfelt Hansen

Ah richtig. Ich nahm an, dass OP an natürlichen Problemen interessiert war. Ich habe meine Antwort bearbeitet.

Jagadish

Schätzen Sie bei einer Auszahlungsmatrix für eine Nullsummenmatrix mit Auszahlungen in [0,1] den Wert des Spiels innerhalb eines Additivs $n\times n$ $\epsilon$ .

Dieses Problem hat einen randomisierten Algorithmus, der in der Zeit abläuft. $O(n\log^2(n)/\epsilon^2)$ abläuft , mit dem (nachweislich) kein deterministischer Algorithmus übereinstimmen kann [ GK95 ].

Siehe auch Effiziente und einfache randomisierte Algorithmen, bei denen der Determinismus schwierig ist .

Neal Young
quelle