Warum gibt es keine Approximationsalgorithmen für SAT und andere Entscheidungsprobleme?

18

Ich habe ein NP-vollständiges Entscheidungsproblem. Angesichts einer bestimmten Instanz des Problems möchte ich einen Algorithmus entwerfen, der JA ausgibt, wenn das Problem durchführbar ist, und NEIN, andernfalls. (Wenn der Algorithmus nicht optimal ist, treten natürlich Fehler auf.)

Ich kann keine Näherungsalgorithmen für solche Probleme finden. Ich habe speziell nach SAT gesucht und in der Wikipedia-Seite über den Approximationsalgorithmus Folgendes gefunden: Eine weitere Einschränkung des Ansatzes besteht darin, dass er nur auf Optimierungsprobleme und nicht auf "reine" Entscheidungsprobleme wie die Erfüllbarkeit zutrifft, obwohl es häufig möglich ist, .. .

Warum definieren wir das Approximationsverhältnis beispielsweise nicht so, dass es proportional zur Anzahl der Fehler ist, die der Algorithmus macht? Wie lösen wir Entscheidungsprobleme tatsächlich gierig und suboptimal?

Ribz
quelle
5
Es gibt Näherungsalgorithmen für MAX-SAT.
Yuval Filmus
2
MAX-SAT ist kein Entscheidungsproblem, oder?
Ribz
15
Näherungsalgorithmen dienen immer Optimierungsproblemen.
Yuval Filmus
4
Sie möchten also im Grunde einen Algorithmus haben, der schnell beendet wird, der jedoch gelegentlich die falsche Antwort geben kann. Ich denke, Sie sind sehr verwirrend, wenn Sie hier genau definierte Begriffe wie "Approximationsalgorithmus" und "optimal" verwenden. Diese haben sehr spezifische Bedeutungen. Ich vermute, Sie suchen stattdessen nach einer Heuristik. Wenn Sie Ihre Frage mit diesem Begriff aktualisieren (oder bei Null anfangen, um noch mehr Verwirrung zu vermeiden), erzielen Sie möglicherweise bessere Ergebnisse.
AnoE
Dies ist zwar keine vollständige Antwort, erklärt aber einen Teil des Grundes: Es gibt wichtige SAT-Probleme, bei denen es nicht besser ist, nur das niedrige Bit falsch zu haben, als die Hälfte der Bits falsch zu sein.
Joshua

Antworten:

33

Approximationsalgorithmen sind nur für Optimierungsprobleme, nicht für Entscheidungsprobleme.

Warum definieren wir das Approximationsverhältnis nicht als den Bruchteil der Fehler, die ein Algorithmus macht, wenn er versucht, ein Entscheidungsproblem zu lösen? Denn "das Näherungsverhältnis" ist ein Begriff mit einer genau definierten Standardbedeutung, der etwas anderes bedeutet, und es wäre verwirrend, denselben Begriff für zwei verschiedene Dinge zu verwenden.

OK, könnten wir ein anderes Verhältnis definieren (nennen wir es etwas anderes - z. B. "das Det-Verhältnis"), das die Anzahl der Fehler eines Algorithmus für ein Entscheidungsproblem quantifiziert? Nun, es ist nicht klar, wie man das macht. Was wäre der Nenner für diesen Bruch? Oder anders ausgedrückt: Es wird unendlich viele Problemfälle geben, und für einige davon gibt der Algorithmus die richtige Antwort und für andere die falsche Antwort, sodass Sie am Ende ein Verhältnis erhalten, das so ist "Etwas geteilt durch die Unendlichkeit", und das endet damit, dass es bedeutungslos oder nicht definiert ist.

Alternativ könnten wir als den Bruchteil von Fehlern definieren, den Algorithmusfehler bei Probleminstanzen der Größe n . Dann könnten wir die Grenze von r n als n berechnen , wenn eine solche Grenze existiert. Das würdernnrnngut definiert sein (falls das Limit existiert). In den meisten Fällen ist dies jedoch möglicherweise nicht besonders nützlich. Insbesondere wird implizit eine gleichmäßige Verteilung auf Probleminstanzen vorausgesetzt. In der realen Welt ist die tatsächliche Verteilung auf Probleminstanzen jedoch möglicherweise nicht einheitlich - sie ist häufig sehr weit von der Einheitlichkeit entfernt. Folglich ist die Zahl, die Sie auf diese Weise erhalten, oft nicht so nützlich, wie Sie vielleicht hoffen: Sie vermittelt oft einen irreführenden Eindruck davon, wie gut der Algorithmus ist.

Um mehr darüber zu erfahren, wie Menschen mit Unlösbarkeit (NP-Härte) umgehen, werfen Sie einen Blick auf Umgang mit Unlösbarkeit: NP-vollständige Probleme .

DW
quelle
3
+1. Aber der letzte Punkt ist nicht eindeutig. Man könnte argumentieren, dass Sie das Approximationsverhältnis als Grenze definieren können, da n die Anzahl der Fehler, die das Programm bei der Eingabe der Länge n macht, über die Anzahl der Zeichenfolgen der Länge n unendlich macht. Dies erweist sich natürlich als nicht sinnvoll, da ein einfaches Programm, das nur "JA" (oder "NEIN") ausgibt, oft ein gutes Verhältnis (manchmal sogar 1!) Erzielt.
Aelguindy
1
@det, das ist eine separate Frage, die Sie separat stellen sollten (nachdem Sie sie in Standardlehrbüchern oder Online-Ressourcen gelesen haben). Wir bevorzugen, dass Sie nur eine Frage pro Post stellen.
DW
1
@aelguindy, guter Punkt. Ich habe meine Antwort entsprechend aktualisiert.
DW
2
@det Warum gierig? Was bedeutet es, ein Entscheidungsproblem "fast" zu lösen?
Raphael
2
@Mehrdad: Normalerweise bewerten Sie einen Approximationsalgorithmus anhand seines Worst-Case-Fehlers: einer Obergrenze dafür, wie nicht optimal er jemals ist. So könnte man beispielsweise sagen, dass ein gegebener Approximationsalgorithmus immer ein Ergebnis findet, das mindestens fünf Sechstel des optimalen Ergebnisses beträgt. Es gibt keine wirkliche Möglichkeit, dies in ein Entscheidungsproblem umzusetzen. wenn Ihr Algorithmus manchmal aussendet (sagen wir) 0,1, dann entweder ist es manchmal weg von 0,9 (in diesem Fall würden Sie besser machen, im schlimmsten Fall, immer emit 0,5), oder die „ungefähre“ -ness ist eine Farce und „0,1 "bedeutet eigentlich nur" 0 ".
Ruakh
14

Der Grund, warum Sie bei Entscheidungsproblemen keine Näherungsverhältnisse sehen, ist, dass sie im Allgemeinen im Kontext der Fragen, die Sie normalerweise zu Entscheidungsproblemen stellen, keinen Sinn ergeben. In einer Optimierungseinstellung ist es sinnvoll, "nah" zu sein. In vielen Umgebungen ist dies nicht sinnvoll. Es ist nicht sinnvoll zu sehen, wie oft Sie in einem diskreten Logarithmusproblem "nah" sind. Es ist nicht sinnvoll zu sehen, wie oft Sie dem Auffinden eines Graph-Isomers "nahe" sind. Ebenso ist es bei den meisten Entscheidungsproblemen nicht sinnvoll, der richtigen Entscheidung "nahe" zu sein.

In der Praxis ist es in vielen Fällen hilfreich zu wissen, welcher Teil der Probleme "schnell" entschieden werden kann und welcher nicht. Im Gegensatz zur Optimierung gibt es jedoch keine einheitliche Methode, um dies zu quantifizieren. Sie können dies statistisch tun, wie Sie vorschlagen, aber nur, wenn Sie die statistische Verteilung Ihrer Eingaben kennen. Die meisten Menschen, die an Entscheidungsproblemen interessiert sind, haben nicht das Glück, solche Verteilungen zu haben.

Betrachten Sie als Fallstudie das Halteproblem. Es ist bekannt, dass das Stopp-Problem nicht zu entscheiden ist. Es ist eine Schande, denn es ist ein sehr nützliches Problem, wenn Sie einen Compiler erstellen. In der Praxis stellen wir jedoch fest, dass sich die meisten Programme aus der Perspektive eines haltenden Problems sehr leicht analysieren lassen. Compiler nutzen dies, um unter diesen Umständen optimalen Code zu generieren. Ein Compiler muss jedoch erkennen, dass die Möglichkeit besteht, dass ein bestimmter Codeblock nicht entscheidbar ist. Jedes Programm, dessen Code "wahrscheinlich entscheidbar" ist, kann in Schwierigkeiten geraten.

Die Metrik, mit der Compiler ermitteln, wie gut sie diese besonderen Fälle des Halteproblems lösen, unterscheidet sich jedoch stark von einer Metrik, mit der ein Kryptografieprogramm testet, ob ein bestimmtes Primzahlenpaar akzeptabel gegen Angriffe abgesichert ist. Es gibt keine Einheitsgröße für alle Lösungen. Wenn Sie eine solche Metrik wünschen, sollten Sie sie an Ihre speziellen Probleme anpassen und die Geschäftslogik berücksichtigen.

Cort Ammon - Setzen Sie Monica wieder ein
quelle
Nach meinem Verständnis besteht die einzige Möglichkeit, ein Entscheidungsproblem zu lösen, darin, den optimalen Algorithmus zu entwerfen, der möglicherweise sehr ineffizient ist. Weil ich ein Entscheidungsproblem (NP-complete) habe und gebeten wurde, einen gierigen (schnellen) Algorithmus zu finden, um eine Lösung zu finden. Wie kann ich das lösen? Kennen Sie einen Artikel, der sich mit solchen Problemen befasst?
Ribz
1
@det Zurückschieben und das Problem erneut beheben lassen. Wenn Sie ein NP-vollständiges Problem haben, stecken Sie ziemlich fest, aber es ist sehr wahrscheinlich, dass Sie eines nicht wirklich lösen müssen. Zum Beispiel brauchen Sie nicht immer die perfekte Antwort. Vielleicht ist nah genug. Oder vielleicht können Sie das Problem für eine Teilmenge von Fällen lösen, die einfach sind, und auf diejenigen stoßen, die schwierig sind. Beispielsweise sind Packungsalgorithmen häufig NP-vollständig, aber Algorithmen, die unter Verwendung probabalistischer Ansätze zuverlässig innerhalb von 5% des Optimums liegen, sind üblich.
Cort Ammon - Reinstate Monica
2
Um ehrlich zu sein, ist die Aufforderung, einen gierigen Algorithmus zur Lösung eines NP-vollständigen Programms zu entwickeln, buchstäblich das Gleiche wie die Aufgabe, die gesamte Gemeinschaft der Informatik / Mathematik in Eigenregie zu übernehmen. Wenn Sie einen Algorithmus für ein NP-vollständiges Programm in P Zeit, am finden sehr dest würden Sie den $ 1 Million Sand Preis für die Lösung von P = NP verdienen. In der Realität würden die Auswirkungen Ihrer Entdeckung das Computing so umgestalten, wie wir es kennen, und die gesamte Sicherheits- / Kryptografieindustrie über Nacht vollständig verändern. Es ist besser, den Wortlaut der Aufgabe so anzupassen, dass er nicht nachweislich NP-vollständig ist.
Cort Ammon - Reinstate Monica
Ich habe einen gierigen exakten Algorithmus für ein NP-vollständiges Problem verwendet. Ich musste nur einen kleinen Fall lösen und konnte mir für ein Wochenende einen 64-Prozessor-Server besorgen.
Patricia Shanahan
8

Lassen Sie mich zusätzlich zu den vorhandenen Antworten darauf hinweisen, dass es Situationen gibt, in denen es sinnvoll ist, eine ungefähre Lösung für ein Entscheidungsproblem zu finden, diese jedoch anders funktioniert, als Sie vielleicht denken.

Mit diesen Algorithmen wird nur eines der beiden Ergebnisse mit Sicherheit bestimmt, während das andere möglicherweise falsch ist. Nehmen Sie zum Beispiel den Miller-Rabin-Test für Primzahlen : Wenn der Test feststellt, dass eine Zahl keine Primzahl ist, ist dieses Ergebnis sicher. Im anderen Fall bedeutet dies jedoch nur, dass die Zahl wahrscheinlich eine Primzahl ist. Je nachdem, wie viel Rechenzeit Sie bereit sind zu investieren, können Sie Ihr Vertrauen in das Ergebnis erhöhen, aber es wird nicht 100% sein, wie es für den Nicht-Prime-Fall ist.

Dies ist besonders hilfreich, wenn Sie unentscheidbare Probleme angehen: Sie können ein Tool schreiben, das versucht, das Problem des Anhaltens eines bestimmten Codeteils zu lösen. Wenn es einen Beweis dafür gibt, dass das Programm keine endlosen Schleifen ausführt, können Sie dies mit 100% iger Sicherheit behaupten. Wenn Sie einen solchen Beweis nicht finden können, kann es sein, dass der Ablauf der Programmsteuerung zu kompliziert ist, um von Ihrem Tool analysiert zu werden, aber es ist kein Beweis dafür, dass er für immer wiederholt wird. Durch die Vereinfachung der Kontrollstrukturen können Sie möglicherweise ein gleichwertiges Programm erstellen, das so einfach ist, dass das Tool nachweisen kann, dass es mit Sicherheit anhält.

ComicSansMS
quelle
Es gibt einen großen Unterschied zwischen probabilistischen (Ihre Antwort) und Approximationsalgorithmen (die Frage). Insbesondere die Kombination beider ist eine ganz besondere Rasse.
Raphael
Wir wissen auch, dass es keine probabilistischen Algorithmen für das Stopp-Problem gibt, sofern der Begriff in diesem Zusammenhang angemessen interpretiert wird.
Raphael
@Raphael Ich hatte nicht die Absicht, dass meine Antwort spezifisch für probabilistische Algorithmen ist. Zugegeben, für Miller-Rabin ist dies der Fall, aber wie Sie selbst erwähnt haben, gilt dies nicht mehr für das Beispiel mit dem Problem des Anhaltens, und ich denke, dies gilt auch nicht für die Mehrzahl der Fälle, in denen Sie dieses Verhalten feststellen. Der Punkt, den ich vermitteln wollte, ist einfach, dass Sie nur über ein Ergebnis Gewissheit bekommen, aber nicht über das andere.
ComicSansMS
Wenn Sie nicht mehr als das sagen, sind einige Probleme nur halb berechenbar, ich denke nicht, dass Sie die Frage beantworten.
Raphael
@Raphael Meine Antwort ist auch nicht spezifisch für halb berechenbare Probleme. In der Tat glaube ich nicht, dass der Ansatz, den ich beschrieben habe, auch auf halb berechenbare Probleme zutrifft. Dort werden Sie nun sicher sein, dass Sie im undefinierten Zweig der Funktion gelandet sind, sodass Sie mit Sicherheit behaupten können, dass es kein Ergebnis gibt. Was ich beschrieben habe, läuft auf Folgendes hinaus: Es könnte eine Antwort geben, aber der Algorithmus hat möglicherweise nicht genau genug ausgesehen, um darüber zu stolpern.
ComicSansMS