Fast immer fast richtig

Ich suche nach einer Komplexitätsklasse, die APX bezieht sich wie BPP P. betrifft Ich habe schon die gleiche Frage gestellt hier , aber vielleicht wäre TCS ein fruchtbarer Ort für Antworten sein.

Der Grund für die Frage ist, dass man in praktischen Problemen häufig ungefähre Antworten (also APX) mit ausreichend hohem Vertrauen (also BPP) finden muss, was die Problemklasse mit begrenzten probabilistischen Approximationsalgorithmen möglicherweise zu einem nützlichen Modell dessen macht, worin berechenbar ist trainieren.

Ein möglicher Kandidat einer solchen Klasse wäre : Probleme, die angenäherte Lösungen mit begrenzten probabilistischen Unterprogrammen zulassen; Ich bin jedoch nicht sicher, ob eine solche Klasse die geeignete Einstellung für die probabilistisch berechenbaren Näherungen der Klasse ist. $APX^{BPP}$

Sowohl BPP als auch APX wurden ausführlich untersucht. Ist dies bei der Fall oder welche Klasse wäre die beste, um die oben genannten Probleme zu erfassen? $APX^{BPP}$

cc.complexity-theory approximation-hardness Michael
quelle

BPP und P sind Entscheidungsproblemklassen. Vielleicht sollten Sie zuerst fragen, welche Funktion / Suchklasse BPP entspricht, bevor Sie zur Approximation übergehen. Ich denke, wenn wir die Funktions- / Suchklasse haben, sollte die Definition der Approximationsversion nicht schwierig sein.

Kaveh

Ich denke, was Sie suchen, ist die Optimierungsversion des PAC-Lernens (wahrscheinlich ungefähr korrekt). Während die Theorie des PAC Lernens speziell über (zufällig, mit hohem wahrscheinlich Korrektheits) ist Lernfunktionen Daten zu beschreiben, wie in maschinellem Lernen, fordern Sie über Optimierungsprobleme. Trotzdem ist die PAC-Lernliteratur vielleicht ein guter Ort, um mit der Suche zu beginnen ...

Joshua Grochow

Anstelle der Orakel-Notation ist das, was Sie beschreiben, näher am BP-Operator. Der BP-Operator wird für Komplexitätsklassen von Entscheidungsproblemen definiert. Es sollte einfach sein, die Definition auf Versprechungsprobleme zu erweitern und auf diese Weise eine Versprechungsproblemversion Ihrer Komplexitätsklasse zu definieren. Das Definieren einer Version für Optimierungsprobleme kann schwieriger sein.

Sasho Nikolov

Antworten:

Für jede gegebene Zielfunktion sei BotL (Best-of-the-List) der Algorithmus, der die Zielfunktion für eine Reihe von Eingaben bewertet und eine Eingabe aus dieser Liste mit maximaler Ausgabe (aus diesen Eingaben) mit Bindungen zurückgibt willkürlich gebrochen. Da APX nur Probleme enthält , deren Zielfunktion in der deterministischen Polynomzeit berechnet werden kann, kann BotL deterministisch in der Polynomzeit implementiert werden. Darüber hinaus ist der von BotL zurückgegebene Wert mindestens so gut wie alle Eingaben, bei denen BotL am wenigsten bewertet wurde. Insbesondere wenn eine der Eingaben in dieser Liste gut genug ist, ist die Ausgabe von BotL gut genug. $\:$
$\:$
$\:$

Daher kann das Ausführen von BotL auf den Ausgängen einer ausreichend großen Anzahl unabhängiger Ausführungen eines Basisalgorithmus die Erfolgswahrscheinlichkeit von 1 / poly auf 1- (1 / (2 ^ poly)) erhöhen.

Infolge des vorhergehenden Absatzes hat das genaue
Konfidenzniveau im Wesentlichen keinen Einfluss auf die resultierende Klasse.
(Diese Situation ist sehr analog zu RP .)

Ich konnte im Komplexitätszoo nichts darüber finden, obwohl
möglicherweise auf dem in diesem Artikel genannten Workshop darüber gesprochen wurde .

quelle

OP fragt nach dem Namen der Klasse von Problemen, die einen randomisierten Algorithmus zur Approximation konstanter Faktoren haben. Sie sagen (glaube ich), dass die Erfolgswahrscheinlichkeit für solche Algorithmen erhöht werden kann. Ich kann nicht sehen, wie dies die Frage beantwortet.

Sasho Nikolov

Ich sehe diese Frage nicht im OP. Michael fragt, ob die Klasse "ausgiebig studiert" wurde. Zugegeben, ich hatte nicht viel zu sagen, aber ich habe (zumindest versucht) ein Missverständnis darüber anzusprechen, was eine solche Klasse sein würde.

$\:$

$\;\;\;$

Es gibt kein solches Missverständnis in der Frage.

Sasho Nikolov

Richtig. Das Missverständnis ist in der "Ein möglicher Kandidat einer solchen Klasse wäre ... wahrscheinlich berechenbare Näherungen." Absatz, der in der Post steht, aber nicht die Frage.

$\:$

$\;\;\;$

Mit den Klarstellungen bin ich immer noch der Meinung, dass Ihre Antwort kein Missverständnis im OP korrigiert, sondern nur eine willkürliche Tatsache über zufällige Annäherungen enthält.

Sasho Nikolov