Está claro que cualquier problema que sea decidible en el espacio de registro determinista ( ) se ejecuta en la mayoría de los casos de polinomios ( ). Hay una gran cantidad de clases de complejidad entre y . Los ejemplos incluyen , , , , , . Se cree ampliamente que .P L P N L L o g C F L N C i S A C i A C i S C i L ≠ P
En una de mis entradas del blog he mencionado dos enfoques (junto con las conjeturas correspondientes) hacia demostrando . ¡Ambos enfoques se basan en programas de ramificación y tienen 20 años de diferencia! ¿Existen otros enfoques y / o conjeturas para separar de (o) separar las clases intermedias entre y ?L P L P
cc.complexity-theory
lower-bounds
space-bounded
Shiva Kintali
fuente
fuente
Respuestas:
Profundidad Circuit límites inferiores (equivalentemente, límites tamaño fórmula inferiores) son probablemente el enfoque más natural: A Super-Iniciar sesión2( n ) la profundidad límite inferior para un problema en PAGS separaría PAGS de L , y la técnica de comunicación complejidad Karchmer-Wigderson puede ser el natural para eso.
fuente
[1] demuestra un límite inferior para instancias de flujo de costo mínimo cuyos tamaños de bits son suficientemente grandes (pero aún lineales) en comparación con el tamaño del gráfico, y además demostró que si se pudiera mostrar el mismo límite inferior para entradas de datos suficientemente pequeños tamaño de bit implicaría (y por lo tanto P ≠ L ). Esto es, en un alto nivel, lo mismo que la respuesta de Noam en que se trata de probar los límites inferiores de la profundidad del circuito (= límites inferiores del tamaño de la fórmula), pero parece ser una dirección muy diferente a los juegos de Karchmer-Wigderson.P ≠ N C P ≠ L
Con más detalle, [1] muestra lo siguiente. Usando la misma notación que en el artículo, dejemos que denote el lenguaje de flujo mincost. Podemos pensar en el lenguaje mincost-flow en gráficos de n -vértices, denotado L ( n ) , como un subconjunto de Z k ( n ) para algunos k ( n ) = Θ ( n 2 ) , con enteros codificados por cadenas de bits . Deje B ( a , n ) denotar el conjunto de todos los vectores en Z k ( n )L norte L ( n ) Zk ( n ) k ( n ) = Θ ( n2) B ( a , n ) Zk(n) donde cada coordenada entera tiene un tamaño de bit como máximo . Dada una función f ( x 1 , ... , x k ) (especificaremos qué tipo de función más adelante), decimos que f separa L ( n ) dentro de B ( a , n ) si los puntos en L ( n ) ∩ B ( a , n ) son exactamente esos → x ∈ B ( a ,an f(x1,…,xk) f L(n) B(a,n) L(n)∩B(a,n) tal que f ( → x ) = 1 .x⃗ ∈B(a,n) f(x⃗ )=1
La relación entre el límite de bits y el límite de tamaño es crucial aquí. En el mismo documento, mostró:2 n / dan 2n/d
La prueba del teorema anterior utiliza algunos martillos pesados como cajas negras, pero por lo demás es elemental (nota: "elemental" " fácil "). Es decir, utiliza el límite de Milnor-Thom en el número de componentes conectados de una variedad semialgebraica real (el mismo límite utilizado por Ben-Or para probar límites inferiores en la distinción / clasificación de elementos en el modelo de árbol de cómputo real), la descomposición de Collins ( se usa para probar la eliminación efectiva del cuantificador sobre R ), un argumento de posición general y algunas otras ideas. Sin embargo, todas estas técnicas sólo dependido del grado de los polinomios involucrados, y así no se puede utilizar para demostrar P ≠ N C como en el anterior Proposition (de hecho, [1, Prop. 7.5] construye un polinomio≠ R P≠NC del mismo grado quemodo que la proposición anterior falla conen lugar de). Analizar esta situación y buscar propiedades que fueran más allá del grado fue una de las inspiraciones para GCT.g g detdet g det
[1] K. Mulmuley. Límites inferiores en un modelo paralelo sin operaciones de bits . SIAM J. Comput., 28 (4), 1460–1509, 1999
fuente
Me alegró el día cuando mi amigo James me dijo que este hilo de hace mucho tiempo se reavivó. Gracias por eso.
Además, tuve la necesidad de compartir algunas referencias interesantes que son relevantes para L vs Log (DCFL) vs Log (CFL). ¡Que tengas un gran día!
http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1
http://link.springer.com/chapter/10.1007/3-540-10003-2_89?no-access=true
http://link.springer.com/chapter/10.1007%2F978-3-642-00982-2_42#page-1
http://www.researchgate.net/publication/220115950_A_Hardest_Language_Recognized_by_Two-Way_Nondeterministic_Pushdown_Automata
fuente
Luca Aceto acaba de destacar este nuevo artículo en su blog como el mejor artículo para estudiantes de EATCS en ICALP 2014 y tiene una nueva forma de separar NL / P:
Resultados de dureza para la intersección sin vacío Wehar
fuente