Gibt es etablierte Komplexitätsklassen mit reellen Zahlen?

Ein Student hat mich kürzlich gebeten, einen NP-Härtenachweis für sie zu prüfen. Sie führten eine Reduktion nach folgenden Grundsätzen durch:

Ich reduziere dieses Problem $P'$ , von dem bekannt ist, dass es NP-vollständig ist, auf mein Problem $P$ (mit einer mehrmaligen Vielfachreduktion), also ist $P$ NP-hart.

Meine Antwort war im Grunde:

Da $P$ Instanzen mit Werten von $\mathbb{R}$ , ist es trivialerweise nicht Turing-berechenbar, sodass Sie die Reduktion überspringen können.

Obwohl dies formal wahr ist, halte ich diesen Ansatz nicht für aufschlussreich: Wir möchten mit Sicherheit in der Lage sein, die "inhärente Komplexität" eines real bewerteten Entscheidungsproblems (oder Optimierungsproblems) zu erfassen und dabei die Einschränkungen zu ignorieren, denen wir beim Umgang mit real gegenüberstehen Zahlen; Die Untersuchung dieser Probleme ist für einen anderen Tag.

Es ist natürlich nicht immer so einfach zu sagen: "Die diskrete Version von Subset Sum ist NP-vollständig, daher ist die kontinuierliche Version auch 'NP-hart'." In diesem Fall ist die Reduktion einfach, aber es gibt berühmte Fälle, in denen die kontinuierliche Version einfacher ist, z. B. lineare oder ganzzahlige Programmierung.

Mir ist aufgefallen, dass sich das RAM-Modell natürlich auf reelle Zahlen erstreckt; Lassen Sie jedes Register eine reelle Zahl speichern und erweitern Sie die Grundoperationen entsprechend. Das einheitliche Kostenmodell ist - wie auch im diskreten Fall - immer noch sinnvoll, das logarithmische nicht.

Meine Frage lautet also: Gibt es etablierte Vorstellungen von der Komplexität realer Probleme? In welcher Beziehung stehen sie zu den diskreten Standardklassen?

^{Google-Suchanfragen liefern einige Ergebnisse, z. B. diese , aber ich kann nicht sagen, was etabliert und / oder nützlich ist und was nicht.}

Ja. Es gibt.

Es gibt das Real-RAM / BSS-Modell, das in der anderen Antwort erwähnt wird. Das Modell hat einige Probleme und AFAIK gibt es nicht viel Forschungstätigkeit darüber. Argumentieren, ist es kein realistisches Modell der Berechnung .

Der aktivere Begriff der realen Berechenbarkeit ist der des Berechnungsmodells eines höheren Typs. Die Grundidee ist, dass Sie Komplexität für Funktionen höherer Typen definieren und dann Funktionen höherer Typen verwenden, um reelle Zahlen darzustellen.

Die Untersuchung der Komplexität höherer Typfunktionen geht mindestens auf [1] zurück. Für die jüngsten Arbeiten lesen Sie die Akitoshi Kawamura- Papiere über die Komplexität der realen Bediener.

Die klassische Referenz für die Komplexität realer Funktionen ist das Buch von Ker-I Ko [2]. Das 6. Kapitel des neueren Buches von Klause Weihrauch [3] befasst sich ebenfalls mit der Komplexität realer Berechnungen (wobei jedoch mehr die Berechenbarkeit als die Komplexität im Vordergrund steht).

• [1] Stephen Cook und Bruce Kapron, "Charakterisierungen der realisierbaren Grundfunktionen vom endlichen Typ", 1990.

• [2] Ker-I Ko, "Computational Complexity of Real Functions", 1991.

• [3] Klaus Weihrauch "Computable Analysis", 2000.

Das von Ihnen beschriebene Modell ist als Blum-Shub-Smale (BSS) -Modell (auch Real-RAM-Modell) bekannt und wird in der Tat zur Definition von Komplexitätsklassen verwendet.

Einige interessante Probleme in diesem Bereich sind die Klassen , N P R und natürlich die Frage, ob P R = N P R ist . Mit P R ist gemeint, dass das Problem polynomiell bestimmbar ist, mit N P R ist das Problem polynomiell überprüfbar. Zu der Klasse N P R gibt es Härte- / Vollständigkeitsfragen . Ein Beispiel für ein N P R- vollständiges Problem ist das Problem von Q P S , quadratisches Polynomsystem, in dem die Eingabe echte Polynome ist$P_R$$NP_R$$P_R$$NP_R$$P_R$$NP_R$$NP_R$$NP_R$$QPS$ Variablen und p 1 , . . . , P n ⊆ R [ x 1 , . . . , x n ] höchstens 2 Grad, und jedes Polynom hat höchstens 3 Variablen. Die Frageob es eine echte Lösung gemeinsam R n , derartdaß p 1 ( a ) , p 2 ( a ) , . . . p n ( a ) = $m$$p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$$R^n$$p_1(a), p_2(a), ... p_n(a) = 0$. Dies ist ein vollständiges Problem.$NP_R$

Interessanter ist jedoch, dass einige Arbeiten über die Beziehung zwischen (Probalistisch überprüfbare Beweise) über die Reals, dh die Klasse P C P R , und deren Beziehung zu den algebraischen Berechnungsmodellen durchgeführt wurden. Das BSS-Modell schwenkt über Real auf N P. Dies ist Standard in der Literatur, und wir wissen heute, dass N P R "transparente lange Beweise" und "transparente kurze Beweise" hat. Mit "transparenten langen Beweisen" ist folgendes gemeint: N P R ist in P C P R enthalten ( p o l $PCP$$PCP_R$$NP$$NP_R$$NP_R$ . Es gibt auch eine Erweiterung, die besagt, dass die "Fast (ungefähre) Kurzversion" auch wahr ist. Können wir den Beweis stabilisieren und Fehler erkennen, indem wir wesentlich weniger (reale) Komponenten als n untersuchen ? Dies führt zu Fragen über die Existenz von Nullen für (System von) univariaten Polynomen, die durch ein Geradenprogramm gegeben sind. Mit "transparenten langen Beweisen" meinen wir auch$PCP_R(poly, O(1))$$n$

1. "transparent" - Nur zu lesen,$O(1)$

2. long - superpolynomielle Anzahl reeller Komponenten.

Der Beweis ist an gebunden , und ein sicherer Weg, um echte Probleme zu betrachten, besteht darin, wie er mit der Teilmenge Summe in Beziehung gesetzt werden könnte - selbst Näherungsalgorithmen für die echten Probleme wären interessant - wie für die Optimierung - lineare Programmierung, die wir kennen ist in der Klasse F P , aber ja, es wäre interessant zu sehen, wie sich die Approximierbarkeit auf die Vollständigkeit / Härte für den Fall von N P R -Problemen auswirken könnte . Eine andere Frage wäre auch N P R = c o - N P R ? $3SAT$$FP$$NP_R$$NP_R$ $=$ $co\text{-}NP_R$

Wenn man an die Klasse denkt , gibt es auch Zählklassen, die definiert sind, um über Polynomarithmetik zu argumentieren. Während # P die über { 0 , 1 } ∞ → N definierte Klasse von Funktionen f ist , für die eine Polynomzeit Turingmaschine M und ein Polynom p mit der Eigenschaft ∀ n ∈ N und x ∈ { 0 , 1 } existieren n , f ( x $NP_R$$\#P$$f$$\{0,1\}^\infty$ $\rightarrow$ $\mathbb{N}$$M$$p$$\forall n$$\in$$\mathbb{N}$$x$$\in$$\{0,1\}^{n}$$f(x)$zählt die Anzahl der Saiten { 0 , 1 } p ( n ) , die die Turing-Maschine M akzeptiert { x , y } . Im Grunde genommen erweitern wir diese Idee um additive BSS-Maschinen - BSS-Maschinen, die nur Additionen und Multiplikationen ausführen (keine Divisionen, keine Subtraktionen). Bei additiven BSS-Maschinen (Knoten in der Berechnung erlauben nur Addition und Multiplikation) wird das Modell für # P zu einem Modell, bei dem die Zählung über den Vektoren liegt, die die additiven BSS-Maschinen akzeptieren. Die Zählklasse lautet also # P a d $y \in$$\{0,1\}^{p(n)}$$M$$\{x,y\}$$\# P$$\#P_{add}$ Diese Klasse ist nützlich für das Studium von Betti-Zahlen und auch der Euler-Charakteristik.