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:
- 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.
- 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.
- 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!
quelle
Antworten:
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.
quelle