Ranking der Schwierigkeit schwerer NP-Probleme in der Praxis

15

Diese Frage hängt eng mit einem anderen Beitrag zusammen: Phasenübergänge bei schwierigen NP-Problemen, aber es ist etwas anders. Während die Frage nach der Härte von bestimmten Instanzen von NP schwer Problemen ist, geht es um Ranking die Schwierigkeit der gleichen Instanzen.

Es gibt eine Menge Literatur zu dem Effekt, der als Phasenübergang bekannt ist . Insbesondere für den Fall von zufälligen 3-SAT-Formeln in Conjunctive Normal Form (CNF) ist bekannt, dass es einen Wert R des Verhältnisses von Klauseln zu Variablen gibt, so dass für alle r <R die Formel mit hoher Wahrscheinlichkeit erfüllt werden kann und für r> R ist die Formel mit hoher Wahrscheinlichkeit nicht erfüllbar. Der Phasenübergangseffekt tritt in der Nähe von R auf und hat den bemerkenswerten Effekt, dass die Lösung des Erfüllbarkeitsproblems für diese Formeln in der Praxis äußerst schwierig ist.

Da zum Nachweis der NP-Härte eines gegebenen Problems gezeigt werden muss, dass es eine Polynomzeit gibt, in der ein NP-vollständiges Problem nach der Turing-Reduktion vorliegt, und dass Probleme, die NP-vollständig sind, in eine Polynomzeit zwischen ihnen transformiert werden können, gilt: Folgende Frage stellt sich natürlich:

Ist es möglich, Rang die Schwierigkeit der NP schwerer Probleme in der Praxis mit der Phasenumwandlung von 3-SAT CNF als Indikator? Die Intuition ist, dass erwartet werden kann, dass ein Problem P1 härter ist als P2, wenn seine 3-SAT-Codierung näher bei R liegt (was bekanntermaßen nahe bei 4,2 liegt). Beachten Sie, dass diese Idee nicht unbedingt jede einzelne Instanz an eine bestimmte Schwierigkeit gebunden ist, sondern sie lediglich einordnet.

Es gibt eine Reihe von Gegenargumenten, darunter:

  1. Die Formel für den Phasenübergang von 3-SAT-CNF gilt für Zufallsformeln. Eine bestimmte Instanz in einem anderen Problem weist jedoch eine Struktur auf, die von Lösern für dieses Problem ausgenutzt werden könnte - darauf hat Peter Shor bereits in der oben genannten Frage hingewiesen.
  2. Es könnte der Fall sein, dass die spezielle Codierung, die für die Transformation der speziellen Instanzen in unserem Problem zu 3-SAT verwendet wird, eine entscheidende Rolle für das Verhältnis von Klauseln zu Variablen spielt, was zu irreführenden Werten und damit zu Fehlklassifizierungen führt die Kommentare zu dieser Frage.
  3. Serge (nach meinem Verständnis aus seinem Kommentar zu dieser Frage) wirft das Problem auf, dass man das ursprüngliche NP-Problem künstlich komplizieren könnte, so dass sich eine 3CNF-Formel ergibt, die das Verhältnis von Klauseln zu Variablen ändert, während die Erfüllbarkeit erhalten bleibt.

Wie bei 1 können alle Probleme die gleiche Regelmäßigkeitsklasse haben, so dass Rangordnungsprobleme (anstatt die Schwierigkeit zu charakterisieren) zutreffen können. wie für 2 gibt es Codierungen, von denen insbesondere bekannt ist, dass sie nicht redundant bezüglich der Einheitsausbreitungsregel sind, so dass diese bevorzugt werden sollten und möglicherweise diese Fehlklassifizierungen vermieden werden. Ein Beispiel ist Sideris et al., 2010 für den Fall der Propositional Planning. Was 3 betrifft , so haben Cheeseman et al., 1991, bereits die Frage untersucht, ob Abbildungen zwischen Problemen den Phasenübergangseffekt bewahren oder nicht, und ihre vorläufigen Experimente scheinen ihre Vermutung zu stützen, vorausgesetzt, man reduziert das ursprüngliche NP-Problem und sogar das kann sein durch Anwendung der Entschließung zu den Klauseln weiter reduziert ".

Ergibt das alles für Sie einen Sinn? Kennen Sie bibliografische Hinweise dazu? Jede Anleitung wäre weitgehend anerkannt!

Carlos Linares López
quelle
Ich würde vermuten, dass die Antwort von der speziellen Reduktion auf SAT abhängt, die man verwendet, obwohl es einen Weg geben könnte, dies zu umgehen.
Kaveh
5
Ein weiteres Gegenargument ist, dass man einer 3CNF-Formel immer eine sehr spärliche oder sehr dichte erfüllbare disjunkte Komponente hinzufügen kann, indem man das Verhältnis von Klauseln zu Variablen ändert und ihre Erfüllbarkeit beibehält.
Serge Gaspers
@Kaveh: vielen Dank für deine Kommentare! Die Idee wäre, nicht redundante Kodierungen für 3-SAT zu verwenden, wie in [Sideris et al. 2010]. Ich behaupte nicht, dass dies funktionieren wird, aber es scheint das Richtige zu sein. Ich habe die Frage mit Ihrem Kommentar bearbeitet. Danke noch einmal!
Carlos Linares López
1
@ Serge: guter Punkt Serge! [Cheesemann et al., 1991] untersuchten bereits die Frage, ob Abbildungen zwischen Problemen den Phasenübergangseffekt sowohl für NP-Probleme als auch für Probleme in P bewahren (um zu beweisen, dass sie nicht NP werden, wenn sie beispielsweise künstlich auf 3-SAT erweitert wurden) ) und ihre Ergebnisse stützen diese Behauptungen, vorausgesetzt, sie beginnen mit einigen vorläufigen Kürzungen, möglicherweise unter Anwendung der Einheitsausbreitungsregel. Ich habe meine Frage mit Ihren Kommentaren bearbeitet. Danke vielmals!
Carlos Linares López
@all: vielen dank für die aufmerksamkeit auf meine frage! Es ist meine erste Frage hier (und ich werde sicherlich in Zukunft andere posten). Ich fand es beeindruckend, dass es in weniger als 24 Stunden 125 Besuche, 7 Stimmen und eine Person erhielt, die es als fav kennzeichneten. Danke an alle!
Carlos Linares López

Antworten:

13

Obwohl es nicht unvorstellbar ist, dass die von Ihnen genannten technischen Hindernisse auf irgendeine Weise überwunden werden können, glaube ich, dass es derzeit nur eine sehr geringe Motivation gibt, dies zu tun, und zwar aus dem einfachen Grund, der die Schwierigkeit von NP-hard (zumindest soweit mir bewusst ist) Probleme in der Praxis scheinen empirisch wenig mit ihrer Nähe zum 3-SAT-Phasenübergang zu tun zu haben.

Vergleichen Sie dies mit einigen anderen Möglichkeiten, um NP-harte Probleme in Bezug auf den Schwierigkeitsgrad einzuordnen: Es gibt eine empirische Korrelation zwischen NP-harten Problemen, die in der Praxis einfach sind, und NP-harten Problemen, die leicht zu approximieren sind oder die mit festen Parametern verfolgt werden können (im Sinne parametrisierter Komplexität). In diesen Fällen wurden geeignete Reduktionsbegriffe entwickelt, die die empirischen Beobachtungen teilweise erklären. Derzeit scheint es jedoch keinen empirischen Hinweis zu geben, dass die meisten in der Praxis schwierigen NP-harten Probleme aufgrund ihrer engen Beziehung zu 3-SAT-Instanzen in der Nähe des Phasenübergangs schwierig sind . Es macht also nicht allzu viel Sinn, eine Theorie zu entwickeln, um etwas zu "erklären", das in der Praxis nicht wahr zu sein scheint.

Timothy Chow
quelle
2
Upvoted. Mich würde ein Verweis auf das empirische Ranking von NP-harten Problemen interessieren.
Aaron Sterling
Auch upvoted! Aber als Aaron würde ich mich auch sehr für ein paar Nachschlagewerke über das Ranking von NP-schwierigen Problemen interessieren. Geben Sie mir ein paar und ich werde diese Frage gerne als beantwortet markieren! (Mit freundlichen Grüßen, ich werde es mit Sicherheit in ein paar Tagen tun, auch wenn Sie keine Bib-Referenzen angeben.) Nochmals vielen Dank, Timothy!
Carlos Linares López
1
@ CarlosLinaresLópez: Grundlagen der parametrisierten Komplexität von Downey und Fellows (Springer, 2013) geben einige Informationen über die Hierarchie der parametrisierten Komplexität. Approximationsalgorithmen für NP-harte ProblemeW von Dorit Hochbaum (Hrsg.) Ordnen einige NP-harte Probleme nach der Schwierigkeit der Approximation. Hochbaums Buch ist ein bisschen alt, daher sollten Sie sich auch neuere Bücher über Approximationsalgorithmen ansehen.
Timothy Chow
Timothy !! Vielen Dank wirklich !!! Es ist sehr nett von Ihnen, diese Startnummer anzugeben !! Ich danke dir sehr!!
Carlos Linares López