E-Book, Englisch, 361 Seiten, eBook
Reihe: Discrete Mathematics and Theoretical Computer Science
Lassaigne / Rougemont Logic and Complexity
2004
ISBN: 978-0-85729-392-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
E-Book, Englisch, 361 Seiten, eBook
Reihe: Discrete Mathematics and Theoretical Computer Science
ISBN: 978-0-85729-392-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
1. Basic model theory and computability.- 1. Propositional logic.- 2. Deduction systems.- 3. First-order logic.- 4. Completeness of first order logic.- 5. Models of computation.- 6. Recursion and decidability.- 7. Incompleteness of Peano arithmetic.- 2. Descriptive Complexity.- 8 Complexity: time and space.- 9. First-order definability.- 10. Inductive definitions and second-order logic.- 11. Time complexity : the classes P and NP.- 12. Models of parallel computations.- 13. Space complexity: the classes L, FL, NL and PSPACE.- 14. Definability of optimization and counting problems.- 3. Approximation and classes beyond NP.- 15. Probabilistic Classes.- 16. Probabilistic verification.- 17. Approximation.- 18. Classes beyond NP.- List of Figures.