NP completitud sobre reales

Estoy estudiando el modelo de computación BSS recientemente (véase, por ejemplo, Complejidad y Computación Real; Blum, Cucker, Shub, Smale).

Para los reales , se muestra que, dado un sistema de polinomios , la existencia de ceros es NP_R -completa. Sin embargo, me pregunto si esas f son polinomios que solo tienen coeficientes enteros, es decir, f_1, \ cdots, f_m \ in Z [x_1, \ cdots, x_n] , ¿sigue siendo el problema NP_R -hard? (obviamente está en NP_R ).f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] N P R$R$$f_1,\cdots, f_m\in R[x_1, \cdots, x_n]$$NP_R$$f$N P R N P $f_1,\cdots, f_m\in Z[x_1, \cdots, x_n]$$NP_R$$NP_R$

Sospecho que sí, pero ¿hay alguna prueba simple?

Creo que la respuesta es no , suponiendo $\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$ (Creo que doy una prueba a continuación, pero hay suficientes posibles cuestiones definitorias puntuales aquí que estoy siendo cauteloso sobre mis afirmaciones).

Prueba de que la respuesta es no asumir$\mathsf{P}_\mathbb{R} \neq \mathsf{NP}_{\mathbb{R}}$ : De hecho, creo que la siguiente afirmación más fuerte es válida:

Lema: Para cualquier problema de decisión de BSS sobre , si poly-time-BSS reduce a un problema en entradas enteras, entonces .R L R L ∈ P $L$$\mathbb{R}$$L$$_{\mathbb{R}}$$L \in \mathsf{P}_\mathbb{R}$

Prueba del lema : Supongamos que había un BSS-tiempo polinómico reducción de a un problema en las entradas de números enteros, dado por una máquina . Para entradas que consisten en parámetros reales, desenrolle el cálculo de en un árbol de cálculo algebraico. Solo hay muchas hojas finitas, y el resultado en cada hoja es una única función racional en los parámetros de entrada. Para que una función racional de entradas reales produzca siempre un valor entero, debe ser una función constante y, por lo tanto, no depender de la entrada. Sin embargo, qué función constante se utiliza en cada hoja puede, por supuesto, depender de las ramas. Sin embargo, dado que es una máquina uniforme, solo puede haber LMnMMO(1)O(1)M$_{\mathbb{R}}$$L$$M$$n$$M$$M$$O(1)$ nodos de salida, y por lo tanto solo valores de salida. Por lo tanto, puede modificarse trivialmente para decidir de hecho en tiempo polinomial. QED$O(1)$$M$$L$

Ahora, tome como factibilidad real de polinomios reales. Si , entonces , y por En el Lema no hay reducción de a ningún problema en las entradas enteras (en particular, a la factibilidad real de los polinomios enteros ).P R ≠ N P R L ∉ P R$L$$\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$$L \notin \mathsf{P}_{\mathbb{R}}$$L$

Promesa problema problema? : Otro problema potencial con su pregunta es que la factibilidad real de los polinomios enteros puede no estar en , sino solo en su versión prometedora. El problema aquí es que verificar que una entrada (como el coeficiente de un polinomio ) es un número entero requiere tiempo que depende de la magnitud de , mientras que el conjunto de instancias (todas las instancias, no solo sí-instancias) para un problema de decisión debe ser decidible en , lo que significa que lleva tiempo polinómico en la cantidad de parámetros f i x N P R P R R xx2xx P r o m i s e N P R N P R N P $\mathsf{NP}_{\mathbb{R}}$$f_i$$x$$\mathsf{NP}_{\mathbb{R}}$$\mathsf{P}_\mathbb{R}$, y no sus magnitudes. Creo que esto está estrechamente relacionado con el hecho de que los enteros no son definibles de primer orden dentro de los reales. (Esencialmente, lo mejor que puede hacer una máquina BSS para probar si una entrada es un número entero es calcular la parte entera de calculando potencias de y haciendo "búsqueda binaria". Una vez que se calcula la parte entera de , solo comprueba si eso es igual a .) Así que creo que el problema de la factibilidad real de las ecuaciones enteras está en pero probablemente no en (o al menos parece no trivial demostrar que está en$_{\mathbb{R}}$$x$$x$$2$$x$$x$$\mathsf{PromiseNP}_{\mathbb{R}}$$\mathsf{NP}_{\mathbb{R}}$$\mathsf{NP}_{\mathbb{R}}$ ).