|
" Logic and Complexity "
by Richard Lassaigne, Michel Rougemont.
| Document Type
|
:
|
BL
|
| Record Number
|
:
|
736723
|
| Doc. No
|
:
|
b556588
|
| Main Entry
|
:
|
by Richard Lassaigne, Michel Rougemont.
|
| Title & Author
|
:
|
Logic and Complexity\ by Richard Lassaigne, Michel Rougemont.
|
| Publication Statement
|
:
|
London: Springer London, 2004
|
| Series Statement
|
:
|
Discrete mathematics and theoretical computer science.
|
| Page. NO
|
:
|
(x, 361 pages)
|
| ISBN
|
:
|
0857293923
|
|
|
:
|
: 9780857293923
|
| 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.
|
| Abstract
|
:
|
Divided into three parts, it covers: - Model Theory and Recursive Functions - introducing the basic model theory of propositional, 1st order, inductive definitions and 2nd order logic.
|
| Subject
|
:
|
Computational complexity.
|
| Subject
|
:
|
Computer science.
|
| Subject
|
:
|
Logic design.
|
| LC Classification
|
:
|
QA267.7B975 2004
|
| Added Entry
|
:
|
Michel Rougemont
|
|
|
:
|
Richard Lassaigne
|
| |