Consecuencias de #P = FP

¿Cuáles serían las consecuencias de #P = FP?

Me interesan las consecuencias prácticas y teóricas.

Desde un punto de vista práctico, estoy particularmente interesado en las consecuencias sobre la Inteligencia Artificial.

Punteros a papeles o libros son más que bienvenidos.

Por favor no digas que #P = FP implica P = NP, eso ya lo sé. Además, no diga "no habrá consecuencias prácticas si el algoritmo se ejecuta a tiempo , donde es el número de electrones en el Universo" $\Omega(n^{\alpha})$ $\alpha$ : permítame suponer que, si existe un algoritmo determinista de tiempo polinómico para un problema # P-completo, su tiempo de ejecución será "clemente" ( , por ejemplo). $O(n^2)$

cc.complexity-theory ds.algorithms complexity-classes counting-complexity ai.artificial-intel Giorgio Camerani
fuente

Respuestas:

Aquí hay algunas consecuencias teóricas de la igualdad FP = # P, aunque no tienen nada que ver con la inteligencia artificial. La suposición FP = # P es equivalente a P = PP , así que permítanme usar la última notación.

Si P = PP, entonces tenemos P = BQP : el cálculo cuántico del tiempo polinomial se puede simular mediante el cálculo clásico y determinista del tiempo polinomial. Esta es una consecuencia directa de BQP⊆PP [ADH97, FR98] (y de un resultado anterior BQP⊆P ^PP [BV97]). Además de mi conocimiento, P = BQP no se deduce del supuesto P = NP. Esta situación es diferente del caso del cálculo aleatorio ( BPP ): dado que BPP⊆NP ^NP [Lau83], la igualdad P = BPP se deduce de P = NP.

Otra consecuencia de P = PP es que el modelo de computación Blum-Shub-Smale sobre los reales con constantes racionales es equivalente a las máquinas de Turing en cierto sentido. Más precisamente, P = PP implica P = BP (P _ℝ⁰ ); es decir, si un lenguaje L ⊆ {0,1} ^* es decidible por un programa libre de constantes sobre los reales en tiempo polinómico, entonces L es decidible por una máquina de Turing de tiempo polinómico. (Aquí "BP" significa "parte booleana" y no tiene nada que ver con BPP). Esto se deduce de BP (P _ℝ⁰ ) ⊆ CH [ABKM09]. Vea el documento para las definiciones. Un problema importante en BP (P _ℝ⁰ ) es el problema de la suma de la raíz cuadraday amigos (por ejemplo, "dado un número entero ky un conjunto finito de puntos de coordenadas enteras en el plano, ¿hay un árbol de extensión de longitud total como máximo k ?") [Tiw92].

De manera similar al segundo argumento, el problema de calcular un bit específico en x ^y cuando los enteros positivos x e y se dan en binario estará en P si P = PP.

Referencias

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen y Peter Bro Miltersen. Sobre la complejidad del análisis numérico. SIAM Journal on Computing , 38 (5): 1987–2006, enero de 2009. http://dx.doi.org/10.1137/070697926

[ADH97] Leonard M. Adleman, Jonathan DeMarrais y Ming-Deh A. Huang. Computabilidad cuántica. SIAM Journal on Computing , 26 (5): 1524–1540, octubre de 1997. http://dx.doi.org/10.1137/S0097539795293639

[BV97] Ethan Bernstein y Umesh Vazirani. Teoría de la complejidad cuántica. SIAM Journal on Computing , 26 (5): 1411–1473, octubre de 1997. http://dx.doi.org/10.1137/S0097539796300921

[FR98] Lance Fortnow y John Rogers. Limitaciones de complejidad en la computación cuántica. Journal of Computer and System Sciences , 59 (2): 240–252, octubre de 1999. http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Clemens Lautemann. BPP y la jerarquía de tiempo polinomial. Cartas de procesamiento de información , 17 (4): 215–217, noviembre de 1983. http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Prasoon Tiwari. Un problema que es más fácil de resolver en la RAM algebraica de costo unitario. Journal of Complexity , 8 (4): 393–397, diciembre de 1992. http://dx.doi.org/10.1016/0885-064X(92)90003-T

Tsuyoshi Ito
fuente

Me ganaste a esto! En realidad, tienes razón sobre BQP vs NP. Parece haber evidencia razonable de que BQP no está contenido en PH (véase, por ejemplo, arxiv.org/abs/0910.4698 ), aunque creo que la Conjetura generalizada de Linial-Nisan que se utiliza en el segundo bit ha demostrado ser incorrecta.

Joe Fitzsimons

@turkistany: Si no me equivoco, P = NP implica P = BPP porque BPP está contenido en PH, y si P = NP entonces P = PH.

Niel de Beaudrap

Por cierto: +1 para (FP = # P) ⇔ (P = PP), incluso dejando de lado el resto del contenido de la respuesta.

Niel de Beaudrap

@ Joe: A la luz de las respuestas a la otra pregunta, creo que la mejor evidencia de "P = NP no implica P = BQP" sin probar P = NP ≠ BQP probablemente sería un resultado de separación de oráculo: "Existe un oráculo A tal que P ^ A = NP ^ A ≠ BQP ^ A ”. Por supuesto, esto no es nada fácil porque ese resultado implicaría BQP ^ A⊈PH ^ A, resolviendo una gran pregunta abierta.

Tsuyoshi Ito

@ Tsuyoshi: ¿No puedes construir tal oráculo a partir de un oráculo con respecto al cual BQP no está contenido en PH, simplemente tomándolo junto con PH para formar un nuevo oráculo?

Joe Fitzsimons

En los modelos gráficos , muchos de los problemas de estimación son # P-completos, porque implican hacer cálculos de suma de productos a la permanente sobre gráficos generales. Si #P = FP, los modelos gráficos de repente se vuelven mucho más fáciles, y ya no tenemos que jugar con modelos de bajo ancho de árbol.

Suresh Venkat
fuente

Toda demostró que cualquier problema en la jerarquía de tiempo polinómico se puede reducir a la función #P. Formalmente, demostró que . Entonces, si entonces el colapsaría y, en consecuencia, las tautologías tendrían pruebas cortas. $PH \subseteq P^{\#P}$ $\sharp P=FP$ $PH$

Mohammad Al-Turkistany
fuente

¿Alguien puede aclarar: esto no es lo mismo que decir "P = PH" (que se seguiría inmediatamente de P = NP)?

Niel de Beaudrap

@Niel: No es lo mismo, es más fuerte.

Giorgio Camerani

P^{FP} = P

$\text P^{\text{FP}} = \text P$

# P = FP

$\#\text P = \text{FP}$

PH \subseteq P^{# P} = P^{FP} = P \subseteq PH

$\text{PH} \subseteq \text P^{\#\text P} = \text P^{\text{FP}} = \text P \subseteq \text{PH}$

@Todos: solo para aclarar --- mi primer comentario anterior fue hacer la siguiente pregunta "¿Es la respuesta de Turquía equivalente a la afirmación de que FP = # P implica P = PH?" Si quisiera saber si FP = # P era equivalente a P = PH, lo habría preguntado en un comentario en la publicación original, no en la respuesta de Turquía.

Niel de Beaudrap

@Niel: Tienes razón. Esto es lo mismo que decir P = PH, que se deduce de P = NP. Por lo tanto, el uso del teorema de Toda no fue necesario, ya que FP = #P ya implica P = NP = PH.

Robin Kothari