Fondamenti logici della complessità delle prove

Recensioni dei lettori

Attualmente non ci sono recensioni dei lettori. La valutazione si basa su 2 voti.

Titolo originale:

Logical Foundations of Proof Complexity

Contenuto del libro:

Questo libro tratta l'aritmetica vincolata e la complessità delle prove proposizionali dal punto di vista della complessità computazionale.

I primi sette capitoli includono il background logico necessario per il materiale e sono adatti a un corso di laurea. A ciascuna delle numerose classi di complessità sono associati sia una teoria del calcolo dei predicati a due ordinamenti, con induzione limitata ai concetti della classe, sia un sistema di prove proposizionali.

Il risultato è un trattamento uniforme di molti sistemi presenti in letteratura, tra cui le teorie di Buss per la gerarchia polinomiale e molti sistemi eterogenei per classi di complessità come AC0, AC0(m), TC0, NC1, L, NL, NC e P.".