Espero que esté familiarizado con el programa de ramificación para comenzar. En aras de la exhaustividad, la siguiente es la definición de un programa de ramificación. Un BP es un gráfico acíclico dirigido cuyos nodos con un grado de salida distinto de cero están etiquetados por variables y otros nodos están etiquetados con algún valor de salida. Hay un nodo especial con cero grados de entrada que se llama nodo de inicio y otro nodo especial con cero grados de salida se llama nodo sumidero. Los bordes están etiquetados por 0 y 1 y un BP se llama determinista si cada nodo, excepto el nodo sumidero, tiene exactamente un borde etiquetado 0 y un borde etiquetado 1.
¿Cómo usamos este BP para el cálculo? Bueno, dada una entrada, uno comenzará desde el nodo de inicio, seguirá las rutas guiadas por el etiquetado de las variables de entrada y, al final, si se alcanza el nodo sumidero, luego acepta la entrada.
Ahora viene la preocupación por el tamaño. Definimos el ancho de un programa de ramificación como el ancho del nivel más grande del BP (dibuje el BP como un gráfico de nivel y descubra el tamaño del nivel más grande).
- ¿Es la matemática un buen título para un programador?
- ¿Qué es un diagrama de máquina de Turing y cómo diseño uno?
- ¿Cuáles son todas las aplicaciones conocidas de las técnicas de optimización de colonias de hormigas?
- ¿Es log n lo mismo que O (nlogn)?
- ¿Cuál es la forma más sencilla de explicar el problema P = NP?
Ahora que conocemos la estructura del programa de ramificación, veamos algunas funciones y veamos cuál debe ser el tamaño de un BP si intenta calcularlo. Si hace un argumento de conteo, resulta que una función aleatoria, con alta probabilidad, necesitará un BP que sea de tamaño exponencial. Eso te hace pensar que la mayoría de las funciones tienen hugh BP informándolas. Pero crear una función explícita que necesite un tamaño súper lineal fue algo difícil. Nechiporuk lo hizo en 1966 y demostró un límite inferior [matemático] \ Omega (n ^ 2 / \ log ^ 2n) [/ matemático] para una función explícita (distinción de elementos). Y luego hubo un largo silencio.
La idea de la investigación es que si no puede probar algo, restrinja la maldita cosa e intente probar en el modelo restringido. Entonces, el siguiente movimiento fue restringir el ancho de BP. Furst et al dijeron que si mantiene el ancho de BP fijo a algo constante, entonces calcular MAJ necesita un BP enorme. En cierto sentido, la intuición es clara. Para la mayoría necesita recordar cuántos 1 y 0 ve y mantener el ancho fijo, parece que solo recuerda constantemente muchos bits de entrada en cada nivel.
Recuerde, la conjetura de Furst et al fue en 1983, casi dos décadas después del resultado de Nechiporuk. Y, como resultado, estaban equivocados. Barrington muestra que en realidad puede calcular MAJ en el programa de bifurcación de ancho-5, es decir, toda la clase [math] \ mathsf {NC} ^ 1 [/ math] está en ancho-5 BP. Bueno, el problema es que no puedes hacerlo en ancho-4. Necesita ancho -5 porque el grupo simétrico (permutación) de 5 elementos es el primer grupo de este tipo que no tiene solución. Cosas increíbles!
Consecuencias: aunque no es trivial de probar, el resultado de Cai y Furst es uno que roba el pastel donde muestra que PSPACE es serializable por LOGSPACE, es decir, cualquier lenguaje en PSPACE puede calcularse utilizando un contador (de ahí el LOGSPACE) y constante memoria.
Vea la encuesta de Boppanna y Sipser para más detalles.
