Alternativer Komplexitätsbegriff basierend auf der Lücke zwischen Brute-Force und dem besten Algorithmus?

Typischerweise haben effiziente Algorithmen eine polynomielle Laufzeit und einen exponentiell großen Lösungsraum. Dies bedeutet, dass das Problem in zweierlei Hinsicht einfach sein muss: Erstens kann das Problem in einer polynomiellen Anzahl von Schritten gelöst werden, und zweitens muss der Lösungsraum sehr strukturiert sein, da die Laufzeit nur in der Anzahl der möglichen Lösungen polylogarithmisch ist.

Manchmal gehen diese beiden Begriffe jedoch auseinander, und ein Problem ist nur im ersten Sinne einfach. Eine gängige Technik für Approximationsalgorithmen und parametrisierte Komplexität besteht beispielsweise darin, (grob) zu beweisen, dass der Lösungsraum tatsächlich auf eine viel kleinere Größe als die naive Definition beschränkt werden kann, und dann mithilfe von Brute-Force die beste Antwort in diesem begrenzten Raum zu finden . Wenn wir von vornherein beschränken uns auf, sagen wir, n ^ 3 mögliche Antworten, aber wir müssen noch jeden überprüfen, dann in einem gewissen Sinn , solche Probleme noch „hart“ sind, dass es keinen besseren Algorithmus als Brute-Force.

Umgekehrt, wenn wir ein Problem mit einer doppelt exponentiellen Anzahl möglicher Antworten haben, es aber nur in exponentieller Zeit lösen können, dann möchte ich sagen, dass ein solches Problem "einfach" ist ("strukturiert" ist möglicherweise besser Wort), da die Laufzeit nur die Größe des Lösungsraums protokolliert.

Kennt jemand einen Artikel, der sich mit Härte befasst, die auf der Lücke zwischen einem effizienten Algorithmus und Brute-Force oder Härte im Verhältnis zur Größe des Lösungsraums basiert?

Ein Problem bei der Formalisierung der Frage ist, dass der Ausdruck "Lösungsraum für Problem A" nicht genau definiert ist. Die Definition eines Lösungsraums erfordert einen Überprüfungsalgorithmus , der bei einer gegebenen Instanz und einer Kandidatenlösung überprüft, ob die Lösung korrekt ist oder nicht. Dann ist der Lösungsraum einer Instanz, die an einen Prüfer gesendet wird, der Satz von Kandidatenlösungen, die die Prüferausgabe "korrekt" machen.

Nehmen wir zum Beispiel das Problem SAT0: Wird es bei einer Booleschen Formel durch die Zuweisung aller Nullen erfüllt? Dieses Problem tritt trivialerweise in polynomialer Zeit auf, aber der Lösungsraum kann je nach verwendetem Verifizierer sehr unterschiedlich sein. Wenn Ihr Prüfer die in Frage kommende Lösung ignoriert und nur prüft, ob für die Instanz nur Nullen zulässig sind, ist der "Lösungsbereich" für jede SAT0-Instanz auf diesem Prüfer trivial: Es sind alle möglichen Lösungen. Wenn Ihr Prüfer prüft, ob die in Frage kommende Lösung eine zufriedenstellende Aufgabe ist, kann der Lösungsraum einer SAT0-Instanz tatsächlich recht komplex sein, wohl so komplex wie der Lösungsraum einer SAT-Instanz.

$t(n,k)$$n$$k$$n$$k$$O(2^k t(n,k))$

$O(2^k t(n,k))$$2^n$

Das Papier zeigt einige interessante Konsequenzen der Verbesserung der Brute-Force-Suche nach einigen Problemen. Selbst eine Verbesserung der Brute-Force-Suche nach "Lösungsräumen in Polynomgröße" hätte interessante Konsequenzen.

Wie würden Sie mit typischen Problemen der dynamischen Programmierung umgehen? Hier passiert häufig, dass der Raum optimaler Lösungen polynomial begrenzt ist, der Raum der Lösungen jedoch nicht. Es scheint also in Ihrem Sinne "einfach" zu sein, weil die Laufzeit im Lösungsraum logarithmisch ist, aber es ist in Ihrem Sinne "schwer", weil alle potenziell optimalen Lösungen mit "Brute Force" durchlaufen werden.

Die Perspektive scheint einige Dinge anzunehmen, wie die Endlichkeit von Lösungsräumen.

Denken Sie beispielsweise an das Problem, eine Voronoi-Tesselation aus einer Reihe von Eingabepunkten zu generieren. Hier gibt es einen unendlich großen Lösungsraum, da jeder Punkt in den Kanten des Diagramms ein Tupel reeller Zahlen ist. Eine Lösung kann jedoch in O (n log (n)) in der Anzahl der Eingabepunkte (für die Ebene) erreicht werden.

Verwandte sind Probleme, die Algorithmen mit Polynomverzögerung zulassen . Die erste Lösung und jede nachfolgende Lösung kann in Polynomzeit erzeugt werden. Johnson, Yannakakis und Papdimitriou diskutieren diesen Rahmen im Zusammenhang mit anderen möglichen Lücken (wie der polynomialen Gesamtzeit): Bei der Generierung aller maximalen unabhängigen Mengen , Information Processing Letters 27 , 119–123, 1988.