Dolné hranice zložitosti pomocou lineárnej algebry

Pôvodný názov:

Complexity Lower Bounds using Linear Algebra

Obsah knihy:

Zatiaľ čo v oblasti horných hraníc (algoritmov) bol dosiahnutý rýchly pokrok, pokrok v oblasti dolných hraníc zložitosti explicitných problémov zostáva napriek intenzívnemu úsiliu v priebehu niekoľkých desaťročí pomalý.

Ako je to prirodzené pri typických výsledkoch nemožnosti, otázky dolných hraníc sú ťažké matematické problémy, a preto je nepravdepodobné, že by sa dali vyriešiť ad hoc útokmi. Namiesto toho sú potrebné techniky založené na matematických pojmoch, ktoré zachytávajú výpočtovú zložitosť.

Dolné hranice zložitosti pomocou lineárnej algebry skúma niekoľko techník na dokazovanie dolných hraníc v booleovskej, algebraickej a komunikačnej zložitosti založených na určitých lineárnych algebraických prístupoch. Spoločnou témou týchto prístupov je štúdium mier robustnosti hodnosti matice, ktoré zachytávajú zložitosť v danom modeli. Vhodne silné dolné hranice takýchto funkcií robustnosti explicitných matíc vedú k dôležitým dôsledkom v príslušných obvodových alebo komunikačných modeloch.

Pochopenie vnútornej výpočtovej zložitosti problémov má v matematike a teoretickej informatike zásadný význam. Dolné hranice zložitosti pomocou lineárnej algebry sú neoceniteľnou príručkou pre každého, kto pracuje v tejto oblasti.