¿Existen clases de complejidad establecidas con números reales?

Un estudiante recientemente me pidió que verificara una prueba de dureza NP para ellos. Realizaron una reducción en la línea de:

Reduzco este problema $P'$ que se sabe que es NP completo a mi problema $P$ (con una reducción múltiple de tiempo múltiple), por lo que $P$ es NP-duro.

Mi respuesta fue básicamente:

Como $P$ tiene instancias con valores de $\mathbb{R}$ , trivialmente no es computable por Turing, por lo que puede omitir la reducción.

Si bien es formalmente cierto, no creo que este enfoque sea perspicaz: ciertamente nos gustaría poder capturar la "complejidad inherente" de un problema de decisión (u optimización) con valor real, ignorando las limitaciones que enfrentamos al tratar con problemas reales. números; investigar estos temas es para otro día.

Por supuesto, no siempre es tan fácil como decir: "la versión discreta de Subset Sum es NP-complete, por lo que la versión continua es 'NP-hard' también". En este caso, la reducción es fácil, pero hay casos famosos de que la versión continua es más fácil, por ejemplo, programación lineal vs.

Se me ocurrió que el modelo RAM naturalmente se extiende a números reales; deje que cada registro almacene un número real y amplíe las operaciones básicas en consecuencia. El modelo de costo uniforme todavía tiene sentido, tanto como en el caso discreto, de todos modos, mientras que el modelo logarítmico no lo tiene.

Entonces, mi pregunta se reduce a: ¿existen nociones establecidas de complejidad de los problemas de valor real? ¿Cómo se relacionan con las clases discretas "estándar"?

^{Las búsquedas en Google arrojan algunos resultados, por ejemplo, esto , pero no tengo forma de decir qué está establecido y / o es útil y qué no.}

Si. Existen.

Existe el modelo RAM / BSS real mencionado en la otra respuesta. El modelo tiene algunos problemas y AFAIK no hay mucha actividad de investigación al respecto. Podría decirse que no es un modelo realista de computación .

La noción más activa de computabilidad real es la de un modelo de computación de tipo superior. La idea básica es que defina la complejidad para funciones de tipo superior y luego utilice funciones de tipo superior para representar números reales.

El estudio de la complejidad de las funciones de tipo superior se remonta al menos a [1]. Para trabajos recientes, consulte los documentos de Akitoshi Kawamura sobre la complejidad de los operadores reales.

La referencia clásica para la complejidad de las funciones reales es el libro de Ker-I Ko [2]. El capítulo 6, el libro más reciente de Klause Weihrauch [3] también analiza la complejidad de la compilación real (pero está más centrada en la computabilidad que en la complejidad).

• [1] Stephen Cook y Bruce Kapron, "Caracterizaciones de los funcionales básicos viables de tipo finito", 1990.

• [2] Ker-I Ko, "Complejidad computacional de las funciones reales", 1991.

• [3] "Análisis computable" de Klaus Weihrauch, 2000.

El modelo que describe se conoce como el modelo Blum-Shub-Smale (BSS) (también modelo Real RAM) y, de hecho, se utiliza para definir clases de complejidad.

Algunos problemas interesantes en este ámbito son las clases , N P R , y por supuesto la cuestión de si P R = N P R . Por P R m variables, y p 1 , . . . , P n ⊆ R [ x 1 , . . . , x n ] de grado como máximo 2, y cada polinomio tiene como máximo 3 variables. La pregunta de si existe una solución real común R $P_R$$NP_R$$P_R$$NP_R$$P_R$ queremos decir que el problema es polinomialmente decidible, es que el problema es polinomialmente verificable. Hay preguntas de dureza / integridad acerca de la clase N P R . Un ejemplo de un problema completo de N P R es el problema de Q P S , sistema polinómico cuadrático, donde la entrada es polinomios reales en$NP_R$$NP_R$$NP_R$$QPS$$m$$p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$$R^n$tal que $p_1(a), p_2(a), ... p_n(a) = 0$. Este es un problema completo de $NP_R$

Pero, lo que es más interesante, se ha trabajado en la relación entre (Pruebas comprobables de forma probalística), sobre los Reales, es decir, la clase P C P R , y cómo se relaciona con los modelos de cálculo algebraico. El modelo BSS abarca todos los N P sobre reales. Esto es estándar en la literatura, y lo que sabemos hoy es que N P R tiene "pruebas largas transparentes" y "pruebas cortas transparentes". Por "pruebas largas transparentes" se implica lo siguiente: N P R está contenido en P C P R ( p o l $PCP$$PCP_R$$NP$$NP_R$$NP_R$ . También hay una extensión que dice que la "versión corta casi (aproximada)" también es cierta. ¿Podemos estabilizar la prueba y detectar fallas inspeccionando considerablemente menos componentes (reales) que n ? Esto lleva a preguntas sobre la existencia de ceros para (sistema de) polinomios univariados dados por el programa de línea recta. Además, por "pruebas largas transparentes" queremos decir$PCP_R(poly, O(1))$$n$

1. "transparente" - Solo, para ser leído,$O(1)$

2. largo: número superpolinómico de componentes reales.

La prueba está vinculada a , y una forma segura de ver los problemas valorados reales es cómo podría estar relacionado con la Suma de Subconjuntos, incluso los algoritmos de aproximación para los problemas valorados reales serían interesantes, como para la optimización, programación lineal que conocemos está en la clase F P , pero sí, sería interesante ver cómo la aproximabilidad podría afectar la integridad / dureza para el caso de problemas de N P R. Además, otra pregunta sería la N P R = c o - N P R ? $3SAT$$FP$$NP_R$$NP_R$ $=$ $co\text{-}NP_R$

Al pensar en la clase , hay clases de conteo también definidas para permitir el razonamiento sobre la aritmética polinómica. Mientras que # P es la clase de funciones f definidas sobre { 0 , 1 } ∞ → N para las cuales existe una máquina de Turing de tiempo polinomial M y un polinomio p con la propiedad que ∀ n ∈ N , y x ∈ { 0 , 1 } 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)$cuenta el número de cadenas { 0 , 1 } p ( n ) que Turing Machine M acepta { x , y } . Para los reales, ampliamos esta idea, hay máquinas BSS aditivas: máquinas BSS que solo suman y multiplican (sin divisiones, sin restas). Con las máquinas BSS aditivas (los nodos en la computación solo permiten la suma y la multiplicación), el modelo para # P se convierte en uno en el que el recuento está sobre los vectores que las máquinas BSS aditivas aceptan. Entonces, la clase de conteo es # P a d $y \in$$\{0,1\}^{p(n)}$$M$$\{x,y\}$$\# P$$\#P_{add}$ Esta clase es útil en el estudio de los números de Betti, y también la característica de Euler.