Hodnocení:
Aktuálně nejsou k dispozici žádné recenze čtenářů. Hodnocení je založeno na 2 hlasů.
Logical Foundations of Proof Complexity
Tato kniha se zabývá omezenou aritmetickou a výrokovou složitostí důkazů z hlediska výpočetní složitosti.
Prvních sedm kapitol obsahuje nezbytné logické pozadí látky a je vhodných pro postgraduální kurz. S každou z mnoha tříd složitosti je spojena jak teorie dvou tříděných predikátových kalkulů s indukcí omezenou na pojmy v dané třídě, tak výrokový důkazový systém.
Výsledkem je jednotné zpracování mnoha systémů v literatuře, včetně Bussových teorií pro polynomiální hierarchii a mnoha různorodých systémů pro třídy složitosti jako AC0, AC0(m), TC0, NC1, L, NL, NC a P.".
