Arithmetic Circuits: A Survey of Recent Results and Open Questions
Die algebraische Komplexitätstheorie untersucht die inhärente Schwierigkeit algebraischer Probleme durch Quantifizierung der minimalen Menge an Ressourcen, die zu ihrer Lösung erforderlich sind. Die grundlegendsten Fragen der algebraischen Komplexität stehen im Zusammenhang mit der Komplexität arithmetischer Schaltungen: Bereitstellung effizienter Algorithmen für algebraische Probleme, Nachweis unterer Schranken für die Größe und Tiefe arithmetischer Schaltungen, Bereitstellung effizienter deterministischer Algorithmen für polynomiale Identitätstests und Suche nach effizienten Rekonstruktionsalgorithmen für durch arithmetische Schaltungen berechnete Polynome.
Arithmetische Schaltkreise: A Survey of Recent Results and Open Questions gibt einen Überblick über das Gebiet der Komplexität arithmetischer Schaltungen. Es werden die wichtigsten Ergebnisse und Techniken auf diesem Gebiet behandelt, wobei der Schwerpunkt auf Arbeiten aus den letzten zwei Jahrzehnten liegt.
Insbesondere werden die klassischen strukturellen Ergebnisse wie VP = VNC2 und die neueren Entwicklungen, die die Bedeutung von Schaltungen mit Tiefe 4 hervorheben, die klassischen unteren Schranken von Strassen und Baur-Strassen und die neueren unteren Schranken für multilineare Schaltungen und Formeln, die Fortschritte auf dem Gebiet der deterministischen Überprüfung polynomieller Identitäten und die Ergebnisse bezüglich der Rekonstruktion arithmetischer Schaltungen erörtert. Außerdem werden viele offene Fragen vorgestellt, die angesichts des derzeitigen Wissensstandes als natürliche "nächste Schritte" betrachtet werden können.
| ISBN: | 9781601984005 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Taschenbuch |
Derzeit verfügbar, auf Lager.
