Kauft uns der Zufall irgendetwas in P?

18

Sei die Klasse der Entscheidungsprobleme mit einem beschränkten zweiseitigen fehlerzufälligen Algorithmus, der in der Zeit O ( f ( n ) ) abläuft .BPTIME(f(n))O(f(n))

Kennen wir jedes Problem , so dass Q B P T I M E ( n k ) aber Q D T I M E ( n k ) ? Ist ihre Nichtexistenz bewiesen?QPQBPTIME(nk)QDTIME(nk)

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

aelguindy
quelle
7
(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
2
Ü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
2
@TsuyoshiIto Danke, ich stimme nicht zu, dass ich die Einstellung auf Probleme in P einschränke , wenn wir die Existenz nicht beweisen, dann wissen wir, dass ist . Vielleicht, B P T I M E ( n k ) P = D T I M E ( n k ) , während B P T I M E ( n k ) D T I M E ( n kP=BPPPBPTIME(nk)P=DTIME(nk) Vermisse ich im Allgemeinen etwas? Könnten Sie bitte auch auf mein Missverständnis bezüglich B P T I M E und Z P T I M EBPTIME(nk)DTIME(nk)BPTIMEZPTIME
hinweisen
2
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
1
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(n2)
Neal Young

Antworten:

10

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 ....
1
hinzugefügte Referenz.
Suresh Venkat
13

Problem : Ein Array besteht aus n 1s und n 0s. Finde ein i so, dass A [ i ] 1 ist.A[1..2n]nniA[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 A [ i ]iA[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
1
Jeder deterministische Algorithmus muss im schlimmsten Fall mindestens Anfragen stellen . 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 k > 0 für SAT oder irgendein Problem in NP beweisen '. Ist das korrekt? Ω(nk)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
6

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

Dieses Problem hat einen randomisierten Algorithmus, der in der Zeit O ( n log 2 ( n ) / ϵ 2 ) abläuft.O(nlog2(n)/ϵ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