Logické základy zložitosti dôkazov

Recenzie čitateľov

Momentálne nie sú žiadne recenzie čitateľov. Hodnotenie je založené na 2 hlasoch.

Pôvodný názov:

Logical Foundations of Proof Complexity

Obsah knihy:

Táto kniha sa zaoberá obmedzenou aritmetickou a výrokovou zložitosťou dôkazov z hľadiska výpočtovej zložitosti.

Prvých sedem kapitol obsahuje potrebné logické východiská pre danú látku a sú vhodné pre postgraduálny kurz. S každou z mnohých tried zložitosti je spojená teória predikátového kalkulu s dvoma triedami, pričom indukcia je obmedzená na pojmy v danej triede, a výrokový dôkazový systém.

Výsledkom je jednotné spracovanie mnohých systémov v literatúre, vrátane Bussových teórií pre polynomickú hierarchiu a mnohých rozdielnych systémov pre triedy zložitosti, ako sú AC0, AC0(m), TC0, NC1, L, NL, NC a P.".