Titre original :
Arithmetic Circuits: A Survey of Recent Results and Open Questions
Contenu du livre :
La théorie de la complexité algébrique étudie la difficulté inhérente des problèmes algébriques en quantifiant la quantité minimale de ressources nécessaires pour les résoudre. Les questions les plus fondamentales en matière de complexité algébrique sont liées à la complexité des circuits arithmétiques : fournir des algorithmes efficaces pour les problèmes algébriques, prouver des limites inférieures sur la taille et la profondeur des circuits arithmétiques, donner des algorithmes déterministes efficaces pour le test d'identité des polynômes, et trouver des algorithmes de reconstruction efficaces pour les polynômes calculés par des circuits arithmétiques.
Circuits arithmétiques : A Survey of Recent Results and Open Questions (Circuits arithmétiques : une étude des résultats récents et des questions ouvertes) passe en revue le domaine de la complexité des circuits arithmétiques. Il couvre les principaux résultats et techniques dans ce domaine, en mettant l'accent sur les travaux des deux dernières décennies.
En particulier, il aborde les résultats structurels classiques, notamment VP = VNC2, et les développements récents soulignant l'importance des circuits de profondeur 4, les limites inférieures classiques de Strassen et Baur-Strassen et les limites inférieures récentes pour les circuits et formules multilinéaires, les progrès réalisés dans le domaine de la vérification déterministe des identités polynomiales et les résultats concernant la reconstruction des circuits arithmétiques. Il présente également de nombreuses questions ouvertes qui peuvent être considérées comme des « prochaines étapes » naturelles compte tenu de l'état actuel des connaissances.
Autres informations sur le livre :
| ISBN : | 9781601984005 |
| Auteur : | |
| Éditeur : | |
| Langue : | anglais |
| Reliure : | Broché |
Achat:
Actuellement disponible, en stock.
