E-Books durchsuchen

Logic and Complexity [2004]

1
Introduction
5
Propositional logic
25
Deduction systems
41
First-order logic
57
Completeness of first order logic
67
Models of computation
83
Recursion and decidability
109
Incompleteness of Peano arithmetic
131
Complexity: time and space
151
First-order definability
175
Inductive definitions and second-order logic
191
Time complexity: the classes P and NP
213
Models of parallel computations
229
Space complexity: the classes L, FL, NL and PSPACE
251
Definability of optimization and counting problems
265
Probabilistic Classes
279
Probabilistic verification
299
Approximation
323
Classes beyond NP
Feedback