Computability and Computational Complexity: An Introduction

Author: Zhang Liao
Publisher:
Publish Date: 2004-07-01
Features: This book is a textbook and reference for learning computational theory, consisting of three parts: computability, formal languages and automata, and computational complexity. It primarily introduces several computational models and their equivalences, as well as fundamental concepts such as the computability of functions, predicates, and languages, formal languages and their corresponding automata models, time and space complexity, NP-completeness, etc. This book can serve as a textbook for undergraduate and graduate students in computer science, a reference for researchers and developers in computer science and technology, and an introductory read for readers interested in computational theory. It is part of the series of textbooks for computer science majors and foundational courses in higher education institutions. This book can serve as a textbook for undergraduate and graduate students in computer science, a reference for researchers and developers in computer science and technology, and an introductory read for readers interested in computational theory.