Logiczne podstawy złożoności dowodu

Opinie czytelników

Obecnie brak opinii czytelników. Ocena opiera się na 2 głosach.

Oryginalny tytuł:

Logical Foundations of Proof Complexity

Zawartość książki:

Książka ta traktuje o arytmetyce ograniczonej i złożoności dowodu propozycjonalnego z punktu widzenia złożoności obliczeniowej.

Pierwsze siedem rozdziałów zawiera niezbędne logiczne tło dla materiału i nadaje się na kurs dla absolwentów. Z każdą z wielu klas złożoności związana jest zarówno teoria rachunku predykatów, z indukcją ograniczoną do pojęć w danej klasie, jak i system dowodu propozycjonalnego.

Rezultatem jest jednolite traktowanie wielu systemów w literaturze, w tym teorii Bussa dla hierarchii wielomianów i wielu różnych systemów dla klas złożoności, takich jak AC0, AC0(m), TC0, NC1, L, NL, NC i P.".