Complexity Lower Bounds using Linear Algebra
Während bei den oberen Schranken (Algorithmen) rasche Fortschritte erzielt wurden, sind die Fortschritte bei den unteren Schranken für die Komplexität expliziter Probleme trotz intensiver Bemühungen über mehrere Jahrzehnte hinweg langsam geblieben.
Wie bei typischen Unmöglichkeitsergebnissen sind Fragen zu unteren Schranken harte mathematische Probleme und können daher wahrscheinlich nicht durch Ad-hoc-Angriffe gelöst werden. Stattdessen sind Techniken erforderlich, die auf mathematischen Begriffen basieren, die die rechnerische Komplexität erfassen.
Complexity Lower Bounds using Linear Algebra gibt einen Überblick über verschiedene Techniken zum Nachweis von unteren Schranken in der booleschen, algebraischen und Kommunikationskomplexität auf der Grundlage bestimmter linearer algebraischer Ansätze. Das gemeinsame Thema dieser Ansätze ist die Untersuchung von Robustheitsmaßen des Matrix-Rangs, die die Komplexität in einem bestimmten Modell erfassen. Angemessen starke untere Schranken für solche Robustheitsfunktionen expliziter Matrizen führen zu wichtigen Konsequenzen in den entsprechenden Schaltungs- oder Kommunikationsmodellen.
Das Verständnis der inhärenten Rechenkomplexität von Problemen ist von grundlegender Bedeutung in der Mathematik und der theoretischen Computerwissenschaft. Complexity Lower Bounds using Linear Algebra ist ein unschätzbares Nachschlagewerk für jeden, der auf diesem Gebiet arbeitet.
| ISBN: | 9781601982421 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Taschenbuch |
Derzeit verfügbar, auf Lager.
