Logické základy složitosti důkazů

Recenze čtenářů

Aktuálně nejsou k dispozici žádné recenze čtenářů. Hodnocení je založeno na 2 hlasů.

Původní název:

Logical Foundations of Proof Complexity

Obsah knihy:

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.".