+612 9045 4394
 
CHECKOUT
$7.95 Delivery per order to Australia and New Zealand
100% Australian owned
Over a hundred thousand in-stock titles ready to ship
Logic and Complexity : Discrete Mathematics and Theoretical Computer Science - Richard Lassaigne

Logic and Complexity

Discrete Mathematics and Theoretical Computer Science

Hardcover Published: 20th January 2004
ISBN: 9781852335656
Number Of Pages: 361

Share This Book:

Hardcover

$293.53
or 4 easy payments of $73.38 with Learn more
Ships in 10 to 15 business days

Earn 587 Qantas Points
on this Book

Other Available Editions (Hide)

  • Paperback View Product Published: 8th October 2012
    Ships in 10 to 15 business days
    $293.53

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.

Introductionp. 1
Basic model theory and computabilityp. 3
Propositional logicp. 5
Propositional languagep. 5
Construction of formulasp. 5
Proof by inductionp. 7
Decomposition of a formulap. 7
Semanticsp. 9
Tautologies. Equivalent formulasp. 10
Logical consequencep. 11
Value of a formula and substitutionp. 11
Complete systems of connectivesp. 15
Normal formsp. 15
Disjunctive and conjunctive normal formsp. 15
Functions associated to formulasp. 16
Transformation methodsp. 17
Clausal formp. 19
OBDD: Ordered Binary Decision Diagramsp. 20
Exercisesp. 23
Deduction systemsp. 25
Examples of tableauxp. 25
Tableaux methodp. 27
Treesp. 28
Construction of tableauxp. 29
Development and closurep. 30
Completeness theoremp. 31
Provable formulasp. 31
Soundnessp. 31
Completenessp. 32
Natural deductionp. 33
Compactness theoremp. 36
Exercicesp. 38
First-order logicp. 41
First-order languagesp. 41
Construction of termsp. 42
Construction of formulasp. 43
Free and bound variablesp. 44
Semanticsp. 45
Structures and languagesp. 45
Structures and satisfaction of formulasp. 46
Valid and equivalent formulasp. 48
Substitutionp. 50
Prenex formulas and Skolem formsp. 51
Prenex formulas and normal formsp. 51
Skolem formsp. 53
Exercisesp. 55
Completeness of first order logicp. 57
Natural deduction sytemp. 57
Soundnessp. 59
Completenessp. 59
Examples of theoriesp. 61
Successor functionp. 62
Discrete successor functionp. 62
Graphsp. 63
Robinson's arithmeticp. 64
Exercisesp. 65
Models of computationp. 67
General model of computationp. 67
Turing machinesp. 68
Deterministic Turing machinesp. 68
Non-deterministic Turing machinesp. 71
Machines with multiple tapesp. 74
Turing machine with oraclesp. 76
Alternating machinesp. 76
Other sequential models of computationp. 78
Finite automatap. 78
RAM: Random Access Machinesp. 80
Exercisesp. 82
Recursion and decidabilityp. 83
Recursive functionsp. 83
Primitive recursive functionsp. 83
Construction of primitive recursive functionsp. 84
Coding sequencesp. 86
Non-primitive recursionp. 87
Recursive functionsp. 88
Church's thesisp. 89
Recursion and computationp. 90
Recursive functions are Turing computablep. 90
Turing computable functions are recursivep. 91
Universal Turing machinep. 93
Recursive systemsp. 95
Equivalence with the recursive functionsp. 98
Implementation of recursive functionsp. 98
Recursion and decidabilityp. 101
Recursive and recursively enumerable setsp. 101
The halting problemp. 103
Reductionsp. 104
The s-m-n and Rice's theoremsp. 105
Exercisesp. 107
Incompleteness of Peano arithmeticp. 109
Arithmetic theory and representable functionsp. 109
Peano arithmeticp. 109
Arithmetical proofsp. 110
Non-standard models of arithmeticp. 111
Representable functionsp. 111
Coding arithmetical proofsp. 114
Coding terms and formulasp. 115
Coding sequences of formulasp. 116
Arithmetical theorems are recursively enumerablep. 116
Undecidability and incompletenessp. 117
The validity problem over finite structuresp. 118
The arithmetical hierarchyp. 120
Exercisesp. 127
Descriptive Complexityp. 129
Complexity: time and spacep. 131
Complexity classesp. 132
Complexity of decision problemsp. 132
Examples of decision problemsp. 135
Complexity of search problemsp. 136
Hierarchies for time and spacep. 139
Simulation of several tapesp. 139
The role of constantsp. 140
Relations between classesp. 140
Hierarchiesp. 141
Non-deterministic space classesp. 143
Other models and measuresp. 147
Random access machinesp. 147
Complexity on general structuresp. 148
Average and smoothed complexitiesp. 148
Other measuresp. 148
Exercisesp. 150
First-order definabilityp. 151
Explicit definitionsp. 151
Definability on a class of structuresp. 152
Partial elementary equivalencep. 153
Ehrenfeucht-Fraïssé gamesp. 154
Logical characterization of r-equivalencep. 156
Applications of Ehrenfeucht-Fraïssé gamesp. 158
Relational structuresp. 160
0-1 Lawp. 162
Loś-Vaught's testp. 163
The theory of almost all relational structuresp. 163
Convergence and 0-1 lawp. 164
Implicit definitionsp. 166
Craig's interpolation theoremp. 166
Beth's definability theoremp. 168
Finite structuresp. 169
Exercisesp. 171
Inductive definitions and second-order logicp. 175
Inductive definitionsp. 175
Inductive systemsp. 176
Fixed point logicp. 178
Substitutionp. 179
Stage comparisonp. 180
Fixed point hierarchyp. 182
Datalogp. 184
Second-order logicp. 186
Second-order formulas and interpretationp. 186
Inductive definitions and second-order logicp. 187
Exercisesp. 189
Time complexity : the classes P and NPp. 191
The class NP and NP-complete problemsp. 191
Polynomial time reductionsp. 192
NP-complete problemsp. 192
Logical characterization of NPp. 199
Examples of definable NP problemsp. 202
The logical characterizations of P and FP classesp. 204
P: the class of global inductive relationsp. 204
FP: the class of global recursive functionsp. 208
Exercisesp. 211
Models of parallel computationsp. 213
The boolean circuitsp. 213
Complexity in parallel modelsp. 217
Other circuitsp. 219
Examples of NC problemsp. 219
Matrix multiplicationp. 219
Csanky's matrix inversion algorithmp. 220
The Parallel RAMp. 223
Exercisesp. 226
Space complexity: the classes L, FL, NL and PSPACEp. 229
The classes L, NL and FLp. 230
NL-complete problemsp. 230
Alternation with space constraintsp. 231
Logical characterization of NLp. 232
Logical characterization of FLp. 236
Sequential space and parallel timep. 241
The parallel time thesisp. 243
P-complete problemsp. 243
The class PSPACEp. 244
The quantified boolean formulas and the class APp. 244
Stochastic satisfiabilityp. 246
Problems with uncertaintyp. 247
Exercisesp. 249
Definability of optimization and counting problemsp. 251
Optimization problemsp. 251
Counting problemsp. 257
The counting classesp. 257
Definability of counting functionsp. 259
Exercisesp. 262
Approximation and classes beyond NPp. 263
Probabilistic Classesp. 265
Probabilistic decision classesp. 265
Error amplificationp. 268
Comparing PP and #Pp. 269
Other probabilistic classesp. 269
Examples of probabilistic algorithmsp. 270
Random walk in an undirected graphp. 270
Perfect matching in a bipartite graphp. 272
Solovay-Strassen primality testp. 275
Exercisesp. 277
Probabilistic verificationp. 279
Interactive proofsp. 280
Examples of interactive protocolsp. 281
The problem of non-isomorphism of graphsp. 281
A protocol for the permanentp. 283
A protocol for QBFp. 285
Multiprover protocolsp. 289
Probabilistic checkable proofs PCPp. 290
A PCP (n3, 1) for 3SATp. 293
Exercisesp. 297
Approximationp. 299
Optimization problemsp. 299
Examples of approximation algorithmsp. 301
Approximation of optimization problemsp. 304
Reductions and completenessp. 309
Non-approximabilityp. 311
Counting problemsp. 314
Approximation of counting problemsp. 314
Approximation of #DNFp. 315
Approximate verificationp. 317
Exercisesp. 320
Classes beyondp. 323
The polynomial hierarchyp. 323
Second-order definabilityp. 323
Relative computabilityp. 324
Alternating machinesp. 326
Generalizations of NPp. 327
The classes <$>oplus<$> P, PP and BPPp. 328
Universal hashingp. 331
The Valiant-Vazirani theoremp. 333
Toda's theoremp. 334
Exponential timep. 338
Exercisesp. 342
Bibliographyp. 343
List of Figuresp. 349
Indexp. 353
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9781852335656
ISBN-10: 1852335653
Series: Discrete Mathematics and Theoretical Computer Science
Audience: General
Format: Hardcover
Language: English
Number Of Pages: 361
Published: 20th January 2004
Publisher: SPRINGER VERLAG GMBH
Country of Publication: GB
Dimensions (cm): 23.39 x 15.6  x 2.24
Weight (kg): 0.7

Earn 587 Qantas Points
on this Book