Komplexitás alsó határai lineáris algebra segítségével

Eredeti címe:

Complexity Lower Bounds using Linear Algebra

Könyv tartalma:

Míg a felső korlátok (algoritmusok) terén gyors előrelépés történt, addig az explicit problémák komplexitásának alsó határai terén a több évtizedes intenzív erőfeszítések ellenére is lassú maradt a fejlődés.

Ahogy az a tipikus lehetetlenségi eredmények esetében természetes, az alsó korlátos kérdések nehéz matematikai problémák, és ezért nem valószínű, hogy ad hoc támadásokkal megoldhatók. Ehelyett a számítási bonyolultságot megragadó matematikai fogalmakon alapuló technikákra van szükség.

A Complexity Lower Bounds using Linear Algebra áttekint számos technikát a Boolean, algebrai és kommunikációs komplexitás alsó határainak bizonyítására, amelyek bizonyos lineáris algebrai megközelítéseken alapulnak. E megközelítések közös témája, hogy olyan mátrixrangú robusztussági mértékeket vizsgálnak, amelyek egy adott modellben megragadják a komplexitást. Az explicit mátrixok ilyen robusztussági függvényeinek megfelelően erős alsó határai fontos következményekhez vezetnek a megfelelő áramköri vagy kommunikációs modellekben.

A problémák eredendő számítási komplexitásának megértése alapvető fontosságú a matematikában és az elméleti informatikában. A Complexity Lower Bounds using Linear Algebra felbecsülhetetlen értékű referencia mindazok számára, akik ezen a területen dolgoznak.