A bizonyítási komplexitás logikai alapjai

Olvasói vélemények

Jelenleg nincsenek olvasói vélemények. Az értékelés 2 olvasói szavazat alapján történt.

Eredeti címe:

Logical Foundations of Proof Complexity

Könyv tartalma:

Ez a könyv a korlátos aritmetikai és a tételes bizonyítási komplexitást a számítási komplexitás szempontjából tárgyalja.

Az első hét fejezet tartalmazza az anyaghoz szükséges logikai hátteret, és alkalmas egy végzős kurzus számára. Számos komplexitási osztály mindegyikéhez kapcsolódik egy-egy kétsoros predikátumkalkulus elmélet, az osztály fogalmaira korlátozott indukcióval, valamint egy tételes bizonyítási rendszer.

Az eredmény a szakirodalomban található számos rendszer egységes kezelése, beleértve Buss s elméleteit a polinomiális hierarchiára és számos különböző rendszert olyan komplexitásosztályokra, mint az AC0, AC0(m), TC0, NC1, L, NL, NC és P.".