Cover Image

Logic and Complexity /

Show other versions (1)

Logic and Complexity looks at basic logic as it is used in Computer Science, and provides students with a logical approach to Complexity theory. With plenty of exercises, this book presents classical notions of mathematical logic, such as decidability, completeness and incompleteness, as well as new...

Full description

Bibliographic Details
Main Author: Lassaigne, Richard
Corporate Author: SpringerLink (Online service)
Other Authors: Rougemont, Michel
Format: eBook
Language:English
Published: London : Springer London, 2004.
Series:Discrete mathematics and theoretical computer science.
Subjects:
Computer science.
Logic design.
Computational complexity.
Mathematical optimization.
Distribution (Probability theory)
Electronic books.
Online Access:Connect to the full text of this electronic book
Table of Contents:
  • 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.