Limiti inferiori di complessità utilizzando l'algebra lineare

Titolo originale:

Complexity Lower Bounds using Linear Algebra

Contenuto del libro:

Mentre sono stati compiuti rapidi progressi sui limiti superiori (algoritmi), i progressi sui limiti inferiori della complessità dei problemi espliciti sono rimasti lenti, nonostante gli intensi sforzi compiuti per diversi decenni.

Come è naturale per i tipici risultati di impossibilità, i limiti inferiori sono problemi matematici difficili e quindi è improbabile che possano essere risolti con attacchi ad hoc. Sono invece necessarie tecniche basate su nozioni matematiche che catturino la complessità computazionale.

Complexity Lower Bounds using Linear Algebra esamina diverse tecniche per dimostrare i limiti inferiori della complessità booleana, algebrica e di comunicazione basate su alcuni approcci algebrici lineari. Il tema comune di questi approcci è lo studio di misure di robustezza del rango delle matrici che catturano la complessità in un determinato modello. Limiti inferiori adeguatamente forti su tali funzioni di robustezza di matrici esplicite portano a importanti conseguenze nei corrispondenti modelli di circuito o di comunicazione.

La comprensione della complessità computazionale intrinseca dei problemi è di fondamentale importanza in matematica e in informatica teorica. Complexity Lower Bounds using Linear Algebra è un riferimento prezioso per chiunque lavori in questo campo.