Aritmetikai áramkörök: A legújabb eredmények és nyitott kérdések áttekintése

Eredeti címe:

Arithmetic Circuits: A Survey of Recent Results and Open Questions

Könyv tartalma:

Az algebrai komplexitáselmélet az algebrai problémák eredendő nehézségét vizsgálja azáltal, hogy számszerűsíti a megoldásukhoz szükséges minimális erőforrás-mennyiséget. Az algebrai komplexitás legalapvetőbb kérdései az aritmetikai áramkörök komplexitásával kapcsolatosak: hatékony algoritmusok biztosítása algebrai problémákra, alsó korlátok bizonyítása az aritmetikai áramkörök méretére és mélységére, hatékony determinisztikus algoritmusok megadása a polinom azonosságvizsgálatra, és hatékony rekonstrukciós algoritmusok megtalálása az aritmetikai áramkörökkel számított polinomokra.

Aritmetikai áramkörök: A Survey of Recent Results and Open Questions (A legújabb eredmények és nyitott kérdések áttekintése) című könyv az aritmetikai áramkörök bonyolultságának területét vizsgálja. A könyv a terület főbb eredményeit és technikáit tárgyalja, hangsúlyt fektetve az elmúlt két évtized munkáira.

Külön kitér a klasszikus szerkezeti eredményekre, köztük a VP = VNC2-re és a legújabb fejleményekre, amelyek kiemelik a 4 mélységű áramkörök fontosságát, Strassen és Baur-Strassen klasszikus alsó határaira, valamint a multilineáris áramkörök és formulák legújabb alsó határaira, a polinomiális azonosságok determinisztikus ellenőrzése terén elért eredményekre, valamint az aritmetikai áramkörök rekonstrukciójára vonatkozó eredményekre. Emellett számos olyan nyitott kérdést is bemutat, amelyek a jelenlegi tudásszint ismeretében természetes "következő lépéseknek" tekinthetők.