Aritmetické obvody: Prehľad najnovších výsledkov a otvorených otázok

Pôvodný názov:

Arithmetic Circuits: A Survey of Recent Results and Open Questions

Obsah knihy:

Teória algebraickej zložitosti skúma vnútornú náročnosť algebraických problémov tým, že kvantifikuje minimálne množstvo prostriedkov potrebných na ich riešenie. Najzákladnejšie otázky v algebraickej zložitosti súvisia so zložitosťou aritmetických obvodov: poskytovanie účinných algoritmov pre algebraické problémy, dokazovanie dolných hraníc veľkosti a hĺbky aritmetických obvodov, poskytovanie účinných deterministických algoritmov pre testovanie identity polynómov a hľadanie účinných rekonštrukčných algoritmov pre polynómy počítané aritmetickými obvodmi.

Aritmetické obvody: Prehľad najnovších výsledkov a otvorených otázok sa zaoberá oblasťou zložitosti aritmetických obvodov. Zahŕňa hlavné výsledky a techniky v tejto oblasti s dôrazom na práce z posledných dvoch desaťročí.

Rozoberá najmä klasické štrukturálne výsledky vrátane VP = VNC2 a nedávny vývoj zdôrazňujúci význam obvodov s hĺbkou 4, klasické dolné hranice Strassena a Baur-Strassena a nedávne dolné hranice pre multilineárne obvody a formuly, pokrok dosiahnutý v oblasti deterministickej kontroly polynomických identít a výsledky týkajúce sa rekonštrukcie aritmetických obvodov. Uvádza aj mnohé otvorené otázky, ktoré možno vzhľadom na súčasný stav poznania považovať za prirodzené "ďalšie kroky".