Ist es eine Regel, dass diskrete Probleme NP-hart sind und kontinuierliche Probleme nicht?

In meiner Informatikausbildung stelle ich zunehmend fest, dass die meisten diskreten Probleme (zumindest) NP-vollständig sind, wohingegen die Optimierung kontinuierlicher Probleme fast immer leicht erreichbar ist, normalerweise durch Gradiententechniken. Gibt es Ausnahmen dazu?

Ein Beispiel , das ich Liebe ist das Problem , bei dem, unterschiedlichen gegebenen , entscheiden , ob: ∫ π - π cos ( a 1 z ) cos ( a 2 z ) ... cos ( a n z $a_1, a_2, \ldots, a_n \in \mathbb{N}$

$\{a_1, \ldots, a_n\}$

$n$

Es gibt viele kontinuierliche Probleme der Form "Test, ob diese kombinatorische Eingabe als geometrische Struktur realisiert werden kann", die für die existentielle Theorie der Realzahlen , ein kontinuierliches Analogon von NP , vollständig sind . Dies impliziert insbesondere, dass diese Probleme eher NP-hart als polynomiell lösbar sind. Beispiele umfassen das Testen, ob ein gegebener Graph ein Einheitsabstandsgraph ist, ob ein gegebener Graph in der Ebene mit geraden Liniensegmentkanten und höchstens einer gegebenen Anzahl von Kreuzungen gezeichnet werden kann oder ob eine gegebene Pseudolinanordnung gestreckt werden kann, um eine Linie zu bilden Anordnung.

Es gibt noch weitere Probleme, die noch schwieriger sind: Zum Beispiel ist die Suche nach einem kürzesten Weg zwischen polyedrischen Hindernissen in 3d PSPACE-vollständig (Canny & Reif, FOCS'87).

Dies beantwortet zwar nicht genau Ihre ursprüngliche Frage, ist jedoch ein (mutmaßliches) Beispiel für eine Art philosophischen Kontrapunkt: ein Problem, bei dem die Darstellung diskret ist, die gesamte Härte jedoch vom „kontinuierlichen“ Aspekt des Problems herrührt.

$A=\{a_1, a_2, \ldots, a_m\}$$B=\{b_1, b_2, \ldots, b_n\}$$\sum_{i=1}^m \sqrt{a_i}\leq\sum_{j=1}^n\sqrt{b_j}$schwer, es wird allgemein vermutet, dass es NP-schwer ist und tatsächlich außerhalb von NP liegt (es gibt, wie in den Kommentaren erwähnt, ausgezeichnete Gründe zu der Annahme, dass es nicht NP-vollständig ist); Die einzige bisher bekannte Einschränkung liegt mehrere Ebenen höher in der Polynom-Hierarchie. Natürlich ist die Darstellung dieses Problems so diskret wie möglich - eine Reihe von Ganzzahlen und eine Ja / Nein-Frage zu ihnen -, aber die Herausforderung besteht darin, dass die Berechnung von Quadratwurzeln mit einer bestimmten Genauigkeit ein einfaches Problem ist, sie jedoch möglicherweise berechnet werden müssen zu hohe (möglicherweise superpolynomielle) Genauigkeit, um die Ungleichung auf die eine oder andere Weise auszugleichen. Dies ist ein „diskretes“ Problem, das in einer überraschenden Anzahl von Optimierungskontexten auftritt und zur eigenen Komplexität beiträgt.

Diskrete Probleme sind in der Regel schwieriger (z. B. LP vs. ILP), aber nicht die Diskretion selbst ist das Problem. Die Einschränkungen beeinflussen, wie Sie Ihre Domain durchsuchen können. Sie können beispielsweise annehmen , dass Sie die Optimierung eines Polynoms effizient durchführen können, aber die Entscheidung über die Konvexität von Quartiken (Polynome 4. Grades) ist NP-schwer .

Das heißt, auch wenn Sie schon irgendwie das Optimum haben, es ist schon NP-schwer zu beweisen, dass Sie am Optimum sind.

Obwohl es für einige populäre Probleme in der Tat wahr ist, denke ich, dass beide Annahmen - je nachdem, was Sie als Optimierungsproblem definieren - nicht wahr sind.

Zunächst einige Definitionen: Die meisten Optimierungsprobleme sind nicht Teil von NP . Zum Beispiel für das Knapsack-Problem : Man kann den Nicht-Determinismus nicht ausnutzen, um die wertvollste Tasche zu konstruieren, einfach weil die verschiedenen nicht-deterministischen Zweige keinen gemeinsamen Speicher haben. NP wird auch als "polynomial verifizierbar" (Überprüfung eines Zertifikats) definiert [1, p. 34]. In diesem Fall ist das Zertifikat beispielsweise eine Tasche : eine Bitfolge, bei der, wenn das i- te Bit gesetzt ist, impliziert wird, dass das i- te Element Teil der Tasche ist. Sie können in der Tat in der Polynomzeit prüfen, ob eine solche Tasche wertvoller ist als ein vorgegebener Schwellenwert (dies ist die Entscheidungsvariante)), aber Sie können - soweit wir wissen - nicht anhand eines einzelnen Beutels (einer Polynomzahl von Beuteln) entscheiden, ob dieser Beutel der wertvollste von allen möglichen Beuteln ist. Das ist ein entscheidender Unterschied zwischen beispielsweise NP und EXP : In EXP können Sie alle möglichen Taschen aufzählen und Buch führen, welche Tasche die beste ist.

Die Entscheidungsvariante der Optimierungsprobleme ist in einigen Fällen Teil von NP , man muss klar zwischen dem Maximierungsgeschmack und dem Entscheidungsgeschmack unterscheiden . Bei der Entscheidungsfindung lautet die Frage: " Bei gegebenem Optimierungsproblem und gebundenem Nutzen gibt es eine Lösung mit einem Nutzen, der größer oder gleich dem gebundenen Nutzen ist " (oder geringfügig modifiziert für ein Minimierungsproblem).

Ich gehe auch davon aus, dass Sie mit NP den (hypothetischen) Teil von NP meinen, der nicht Teil von P ist . Wenn P = NP ist , existiert NP-complete natürlich noch, aber es wird gleich P sein (fällt nur mit P für einige Reduktionsbegriffe zusammen, wie polynomielle Vielfachreduktionen von @ AndrásSalamon), was nicht so beeindruckend ist ( und würde die " Lücke " verringern, die Sie in Ihrer Frage angeben).

Ich stelle zunehmend fest, dass die meisten diskreten Probleme NP-vollständig sind.

Jetzt haben wir das geklärt: Es gibt viele Optimierungsprobleme in P : Problem mit dem kürzesten Pfad, Problem mit dem maximalen Durchfluss (für integrale Kapazitäten), minimaler Spannbaum und maximale Anpassung . Obwohl diese Probleme für Sie "trivial zu lösen" scheinen, handelt es sich dennoch um Optimierungsprobleme, und in vielen Fällen ist die Konstruktion (und der Nachweis der Richtigkeit) nicht so einfach. Die Behauptung hält also nicht alle diskreten Probleme für NP-vollständig. Da P nicht gleich NP ist , können diese Probleme nicht NP-vollständig sein .

$\Sigma^P_i$

Während die Optimierung kontinuierlicher Probleme fast immer leicht erreichbar ist.

Ein populäres kontinuierliches Problem, das NP-schwer ist, ist die quadratische Programmierung .

$\vec{x}$

Eigentlich galt die lineare Programmierung lange Zeit auch als NP-hart , jedoch mit sehr guten Heuristiken (die Simplex- Methode). Karmarkar-Algorithmus ist jedoch in P .

Ab dem Moment, in dem sich das Optimierungsproblem mit nicht konvexen Objekten befasst, wird es im Allgemeinen schwierig - wenn nicht unmöglich - sein, einen effizienten Algorithmus zu finden.

Literaturverzeichnis

[1] Computational Complexity, ein moderner Ansatz , Sanjeev Arora und Boaz Barak