Logic and Complexity - Tapa blanda

Sinopsis

Part 1. Basic Model Theory and Computability Propositional logic Deduction systems First order logic Completeness of first-order logic Models of computation Recursion and decidability Incompleteness of Peano Arithmetic Part 2. Descriptive Complexity Complexity: time and space First order definability Inductive definitions and second order logic Models of parallel computations Space complexity: the classes L, FL, NL, PSPACE Definability of optimisation and counting problems Part 3. Approximation and classes beyond NP Probabilistic classes Probabilistic verification Approximation Classes above NP

"Sinopsis" puede pertenecer a otra edición de este libro.