Límites inferiores de complejidad mediante álgebra lineal

Título original:

Complexity Lower Bounds using Linear Algebra

Contenido del libro:

Mientras que se ha avanzado rápidamente en los límites superiores (algoritmos), el progreso en los límites inferiores de la complejidad de los problemas explícitos ha seguido siendo lento a pesar de los intensos esfuerzos realizados durante varias décadas.

Como es natural con los típicos resultados de imposibilidad, las cuestiones de límites inferiores son problemas matemáticos difíciles y, por tanto, es improbable que se resuelvan mediante ataques ad hoc. En su lugar, son necesarias técnicas basadas en nociones matemáticas que capturen la complejidad computacional.

Complexity Lower Bounds using Linear Algebra estudia varias técnicas para demostrar límites inferiores en complejidad booleana, algebraica y de comunicación basadas en ciertos enfoques algebraicos lineales. El tema común entre estos enfoques es el estudio de medidas de robustez del rango de la matriz que capturan la complejidad en un modelo dado. Los límites inferiores de estas funciones de robustez de matrices explícitas, si son suficientemente fuertes, tienen consecuencias importantes en los modelos de circuitos o comunicaciones correspondientes.

Comprender la complejidad computacional inherente a los problemas es de importancia fundamental en matemáticas e informática teórica. Complexity Lower Bounds using Linear Algebra es una referencia inestimable para cualquiera que trabaje en este campo.