Arithmetic Circuits: Un estudio de resultados recientes y preguntas abiertas

Título original:

Arithmetic Circuits: A Survey of Recent Results and Open Questions

Contenido del libro:

La teoría de la complejidad algebraica estudia la dificultad inherente de los problemas algebraicos cuantificando la cantidad mínima de recursos necesarios para resolverlos. Las cuestiones más fundamentales de la complejidad algebraica están relacionadas con la complejidad de los circuitos aritméticos: proporcionar algoritmos eficientes para problemas algebraicos, demostrar límites inferiores en el tamaño y la profundidad de los circuitos aritméticos, proporcionar algoritmos deterministas eficientes para la comprobación de identidades polinómicas y encontrar algoritmos de reconstrucción eficientes para polinomios calculados mediante circuitos aritméticos.

Circuitos aritméticos: A Survey of Recent Results and Open Questions estudia el campo de la complejidad de los circuitos aritméticos. Abarca los principales resultados y técnicas en este campo, haciendo hincapié en los trabajos de las dos últimas décadas.

En particular, se analizan los resultados estructurales clásicos, como VP = VNC2 y los desarrollos recientes que destacan la importancia de los circuitos de profundidad 4, los límites inferiores clásicos de Strassen y Baur-Strassen y los límites inferiores recientes para circuitos y fórmulas multilineales, los avances realizados en el ámbito de la comprobación determinista de identidades polinómicas y los resultados relativos a la reconstrucción de circuitos aritméticos. También presenta muchas cuestiones abiertas que pueden considerarse como "próximos pasos" naturales, dado el estado actual de los conocimientos.