Titre original :
Complexity Lower Bounds using Linear Algebra
Contenu du livre :
Alors que des progrès rapides ont été réalisés sur les limites supérieures (algorithmes), les progrès sur les limites inférieures de la complexité des problèmes explicites sont restés lents malgré les efforts intenses déployés pendant plusieurs décennies.
Comme c'est naturellement le cas pour les résultats d'impossibilité typiques, les questions relatives aux bornes inférieures sont des problèmes mathématiques difficiles et il est donc peu probable qu'elles puissent être résolues par des attaques ad hoc. Au lieu de cela, des techniques basées sur des notions mathématiques qui capturent la complexité de calcul sont nécessaires.
Complexity Lower Bounds using Linear Algebra passe en revue plusieurs techniques pour prouver des bornes inférieures dans la complexité booléenne, algébrique et de communication, basées sur certaines approches d'algèbre linéaire. Le thème commun à ces approches est l'étude des mesures de robustesse du rang de la matrice qui capturent la complexité dans un modèle donné. Des bornes inférieures suffisamment fortes sur de telles fonctions de robustesse de matrices explicites conduisent à des conséquences importantes dans les modèles de circuit ou de communication correspondants.
La compréhension de la complexité informatique inhérente aux problèmes est d'une importance fondamentale en mathématiques et en informatique théorique. Complexity Lower Bounds using Linear Algebra est une référence inestimable pour tous ceux qui travaillent dans ce domaine.
Autres informations sur le livre :
| ISBN : | 9781601982421 |
| Auteur : | |
| Éditeur : | |
| Langue : | anglais |
| Reliure : | Broché |
Achat:
Actuellement disponible, en stock.
