Computability and complexity. Foundations and tools for pursuing scientific applications (Q6549533)

The author delivers a thorough, fundamental textbook on computability and complexity. Following a background chapter setting the baseline for essential concepts on set theory, with notions on countable and uncountable sets, the author splits the chapters into two parts: Part 2 is on computability theory (comprising four chapters) and Part 3 is on computational complexity theory (comprising five chapters). In Part 2 the focus is on \textbf{regular languages and finite automata} (Chapter 2), for which the pumping lemma and the Rabin-Scott theorem are presented, \textbf{general models of computation} (Chapter 3), revolving around Turing machines (the universal Turing machine and the Church-Turing thesis are presented in detail) and partial recursive functions, \textbf{undecidable problems} (Chapter 4), detailing the halting problem, Minsky machines, the generalised Collatz functions and unsolvable word problems, and Chapter 5 describing \textbf{deeper computability} concepts, such as the recursion theorem, the wait-and-see arguments and Turing reducibility.\N\NThe first chapter in Part 3 focuses on computational complexity (Chapter 6). The concepts of polynomial time and space support the overview of the hierarchy theorems. Next, in Chapter 7, NP- and PSPACE completeness is addressed, with concepts and exercises on machine NP-complete problems and the Cook-Levin theorem. Chapters 8 and 9 focus on structural complexity, oracles and Ladner's theorem and on parametrised complexity, respectively. Parametric intractability, parametrised tractability and kernelization lower bounds are discussed in detail. The textbook concludes with Chapter 10, detailing other approaches for coping with hardness, such as approximation algorithms, and the analysis of average-case and generic-case complexity.\N\NThe textbook achieves a balance between theoretical concepts and numerous examples and exercises, scattered efficiently throughout the chapters. Solutions and hints to the exercises are also included. The comprehensive set of references also increase the usefulness of the book. Due to its structure, it is suitable for a wide range of audiences, from students to researchers, and it represents a fundamental stepping stone towards expanding knowledge in the field.