NP-Vollständigkeit über Real

13

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 mR [ 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 mZ [ x 1 , , x n ].Rf1,,fmR[x1,,xn]NPRff1,,fmZ[x1,,xn], ist noch das Problem -hart? (es ist offensichtlich in N P R ).NPRNPR

Ich vermute ja, aber gibt es einen einfachen Beweis?

maomao
quelle

Antworten:

3

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).PRNPR

Beweis, dass die Antwort keine Annahme ist PRNPR : 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 .LRLRLPR

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 gebenRLMnMM Ausgabeknoten und somit nur O ( 1 ) Ausgabewerte. Somitkann M trivial modifiziert werden, um tatsächlich L in der Polynomzeit zubestimmen. QEDO(1)O(1)ML

Nehmen wir nun als echte Machbarkeit realer Polynome. Wenn P RN 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).LPRNPRLPRL

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ötigtNPRfixNPRPRund 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 NRxx2xxPromiseNPR (oder zumindest scheint es nicht trivial zu sein, zu beweisen, dass es sich um N P R handelt ).NPRNPR

Joshua Grochow
quelle