NP-Vollständigkeit über Real

Ich beschäftige mich kürzlich mit dem BSS-Berechnungsmodell (vgl. Zum Beispiel Complexity and Real Computation; Blum, Cucker, Shub, Smale).

Für reelle ist gezeigt, dass bei gegebenem System von Polynomen f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] die Existenz von Nullen N P R -komplett ist. Ich frage mich jedoch, ob diese f Polynome nur ganzzahlige Koeffizienten haben, dh f 1 , ⋯ , f m ∈ Z [ x 1 , ⋯ , x n$R$$f_1,\cdots, f_m\in R[x_1, \cdots, x_n]$$NP_R$$f$$f_1,\cdots, f_m\in Z[x_1, \cdots, x_n]$, ist noch das Problem -hart? (es ist offensichtlich in N P R ).$NP_R$$NP_R$

Ich vermute ja, aber gibt es einen einfachen Beweis?

Ich denke, die Antwort ist nein , wenn man davon ausgeht, dass (ich glaube, ich gebe unten einen Beweis, aber hier gibt es genügend potenziell nicht wählerische Definitionsprobleme, bei denen ich vorsichtig mit meinen Behauptungen bin).$\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$

Beweis, dass die Antwort keine Annahme ist $\mathsf{P}_\mathbb{R} \neq \mathsf{NP}_{\mathbb{R}}$ : Tatsächlich glaube ich, dass die folgende stärkere Aussage gilt:

Lemma: Für jedes BSS-Entscheidungsproblem über R wird L ∈ P R , wenn L poly-time-BSS R auf ein Problem bei ganzzahligen Eingaben reduziert wird .$L$$\mathbb{R}$$L$$_{\mathbb{R}}$$L \in \mathsf{P}_\mathbb{R}$

Beweis des Lemmas : Nehmen wir an, es gäbe eine polynomielle BSS R -Reduktion von L auf ein Problem bei ganzzahligen Eingaben, das von einer Maschine M gegeben wurde . Rollen Sie für Eingaben, die aus n reellen Parametern bestehen, die Berechnung von M in einen algebraischen Berechnungsbaum ab. Es gibt nur endlich viele Blätter, und das Ergebnis bei jedem Blatt ist eine einzelne rationale Funktion in den Eingabeparametern. Damit eine rationale Funktion realer Eingaben immer einen ganzzahligen Wert ausgibt, muss sie eine konstante Funktion sein und ist daher nicht von der Eingabe abhängig. Welche konstante Funktion an jedem Blatt verwendet wird, kann natürlich von den Zweigen abhängen. Da M jedoch eine einheitliche Maschine ist, kann es nur O geben$_{\mathbb{R}}$$L$$M$$n$$M$$M$ Ausgabeknoten und somit nur O ( 1 ) Ausgabewerte. Somitkann M trivial modifiziert werden, um tatsächlich L in der Polynomzeit zubestimmen. QED$O(1)$$O(1)$$M$$L$

Nehmen wir nun als echte Machbarkeit realer Polynome. Wenn P R ≤ N P R ist , dann ist L ≤ P R und durch das Lemma gibt es keine Reduktion von L auf irgendein Problem bei ganzzahligen Eingaben (insbesondere auf die Realisierbarkeit von ganzzahligen Polynomen).$L$$\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$$L \notin \mathsf{P}_{\mathbb{R}}$$L$

Versprichst du ein Problem? : Ein weiteres mögliches Problem bei Ihrer Frage ist, dass die Realisierbarkeit von ganzzahligen Polynomen möglicherweise nicht in , sondern nur in der Versprechungsversion vorliegt. Das Problem hierbei ist , dass zu überprüfen, ob eine Eingabe (wie der Koeffizient eines Polynom f i ) eine ganze Zahl braucht Zeit , die von der Größe abhängt x , während die Menge der Instanzen (alle Instanzen, nicht nur Ja-Instanzen) für Ein N P R -Entscheidungsproblem sollte in P R entscheidbar sein , wobei letzteres bedeutet, dass die Anzahl der Parameter eine polynomielle Zeit benötigt$\mathsf{NP}_{\mathbb{R}}$$f_i$$x$$\mathsf{NP}_{\mathbb{R}}$$\mathsf{P}_\mathbb{R}$und nicht ihre Größen. Dies hängt meines Erachtens eng mit der Tatsache zusammen, dass die ganzen Zahlen innerhalb der Realzahlen nicht in erster Ordnung definierbar sind. ( Im Wesentlichen der besten ein BSS R -Maschine kann zu Test tun , wenn eine Eingabe x eine ganze Zahl ist , den ganzzahligen Teil zu berechnen x durch Kräfte der Berechnung 2 und tun „binäre Suche“ . Sobald sie den ganzzahligen Teil von berechnet ist x , es prüft nur, ob das gleich x ist .) Also denke ich, das Problem der Realisierbarkeit von Ganzzahlgleichungen ist in P r o m i s e N P R, aber wahrscheinlich nicht in N$_{\mathbb{R}}$$x$$x$$2$$x$$x$$\mathsf{PromiseNP}_{\mathbb{R}}$ (oder zumindest scheint es nicht trivial zu sein, zu beweisen, dass es sich um N P R handelt ).$\mathsf{NP}_{\mathbb{R}}$$\mathsf{NP}_{\mathbb{R}}$