¿Qué problemas se sabe que pertenecen a pero que no se sabe que pertenecen a P ?
Más precisamente, estoy interesado en problemas independientes , es decir, cuyas desviaciones aleatorias no son equivalentes. Por ejemplo, se sabe que desrandomizar PIT y factorización polinomial multivariante son equivalentes y los consideraría como un solo problema.
La motivación de mi pregunta es que es común decir que "hay pocos problemas en no se sabe que están en P " , pero no pude encontrar una lista de ellos. En particular, si tengo que citar problemas en esta categoría, generalmente cito la factorización de polinomios univariados sobre campos finitos, o la factorización de polinomios multivariados. Supongo que existen ejemplos que no están relacionados con la factorización polinómica, por ejemplo en otros dominios como la teoría de grafos o la teoría del lenguaje formal.
PD: Me parece curioso que todavía no exista una pregunta similar en este sitio web. ¡Mis disculpas si simplemente no lo encontré (o ellos)!
fuente
Respuestas:
Si está pidiendo problemas independientes, ¿qué tal si:
Es abrumadoramente probable que si realmente tuviera un algoritmo polinómico para resolver el primero de estos, tendría un algoritmo polinómico para todos ellos. Pero no veo cómo reducir formalmente ninguno de estos a ninguno de los otros. Por supuesto, el problema
resuelve todo esto.
fuente
Dicho esto, solo puedo pensar en dos casos en los que este uso conduciría a una diferencia entre BPP y P.
El primero es el algoritmo reciente para los dos caminos más cortos disjuntos ( PDF del autor ), Björklund y Husfeldt, ICALP 2014.
fuente
No soy un experto, pero quizás algunos ejemplos (¿no tan naturales?) Pueden derivarse directamente usando la técnica de reducción determinista de los problemas de búsqueda de BPP a problemas de decisión de BPP , presentados en:
Oded Goldreich, En un mundo de P = BPP. Estudios en Complejidad y Criptografía 2011: 191-232
El teorema puede extenderse a problemas generales de construcción, por ejemplo (ver Corolario 3.9 ) considere el problema de encontrar una prima en un intervalo lo suficientemente grande:
El algoritmo aleatorizado se ejecuta en el tiempo polinómico esperado; no se conoce un algoritmo determinista de tiempo polinómico; pero si BPP = P dicho algoritmo de tiempo polinómico determinista debe existir (porque puede reducirse a un problema de decisión de BPP).
fuente