Fundamentele logice ale complexității probelor

Recenzii ale cititorilor

În prezent, nu există recenzii ale cititorilor. Evaluarea se bazează pe 2 voturi.

Titlul original:

Logical Foundations of Proof Complexity

Conținutul cărții:

Această carte tratează aritmetica delimitată și complexitatea probelor propoziționale din punctul de vedere al complexității computaționale.

Primele șapte capitole includ contextul logic necesar pentru material și sunt potrivite pentru un curs universitar. Fiecăreia dintre numeroasele clase de complexitate îi sunt asociate atât o teorie a calculului predicatului cu două sorți, cu inducție limitată la conceptele din clasă, cât și un sistem de dovezi propoziționale.

Rezultatul este un tratament uniform al multor sisteme din literatură, inclusiv teoriile lui Buss pentru ierarhia polinomială și multe sisteme disparate pentru clase de complexitate, cum ar fi AC0, AC0(m), TC0, NC1, L, NL, NC și P.".