Logic and Complexity

Richard Lassaigne, Michel de Rougemont - Collection Discrete Mathematics and Computer Science

360 pages, parution le 12/02/2004

Ajouter à une liste

Indisponible

Résumé

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 ideas brought by complexity theory such as NP-completeness, randomness and approximations, providing a better understanding for efficient algorithmic solutions to problems.

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. Recursive functions, Turing computability and decidability are also examined.

Descriptive Complexity - looking at the relationship between definitions of problems, queries, properties of programs and their computational complexity.

Approximation - explaining how some optimization problems and counting problems can be approximated according to their logical form.

Logic is important in Computer Science, particularly for verification problems and database query languages such as SQL. Students and researchers in this field will find this book of great interest.

Written for:
4th year undergraduate students, postgraduate students, researchers, industry

L'auteur - Richard Lassaigne

Autres livres de Richard Lassaigne

Logique et complexité

Découvrir tous les livres de Richard Lassaigne

L'auteur - Michel de Rougemont

Autres livres de Michel de Rougemont

Logique et complexité

Découvrir tous les livres de Michel de Rougemont

Sommaire

Part 1. Basic model theory and computability 3
- 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
- Time complexity : the classes P and NP
- Models of parallel computations
- Space complexity: the classes L
- Definability of optimization and counting problems
- Approximation and classes beyond NP
- Probabilistic Classes
- Probabilistic verification
- Approximation
- Classes beyond NP

List of Figures
Index

Voir tout

Replier

Caractéristiques techniques

	PAPIER
Éditeur(s)	Springer
Auteur(s)	Richard Lassaigne, Michel de Rougemont
Collection	Discrete Mathematics and Computer Science
Parution	12/02/2004
Nb. de pages	360
Format	16 x 24
Couverture	Relié
Poids	640g
Intérieur	Noir et Blanc
EAN13	9781852335656
ISBN13	978-1-85233-565-6