Ebook Computational Complexity: A Modern Approach - Part 1

This book "Computational complexity: A modern approach" aims to describe such recent achievements of complexity theory in the context of more classical results. It is intended to both serve as a textbook and as a reference for self-study. Part 1 of book provide students with knowledge about: basic complexity classes; the computational model - and why it doesn’t matter; NP and NP completeness; the polynomial hierarchy and alternations;...

Từ khóa: Computational complexity, Computational complexity theory, Basic complexity classes, The computational model, Non-deterministic Turing machines, The Cook-Levin Theorem, Time Hierarchy Theorem