Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2024 | Book

Some Naive Set Theory Read chapter Read first chapter

Computability and Complexity

Foundations and Tools for Pursuing Scientific Applications

Author: Rod Downey

Publisher: Springer Nature Switzerland

Book Series : Undergraduate Topics in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This is a book about computation, something which is ubiquitous in the modern world. More precisely, it examines computability theory and computational complexity theory. Computability theory is the part of mathematics and computer science which seeks to clarify what we mean by computation or algorithm. When is there a computational solution possible to some question? How can we show that none is possible? How computationally hard is the question we are concerned with? Arguably, this area lead to the development of digital computers. (Computational) complexity theory is an intellectual heir of computability theory. Complexity theory is concerned with understanding what resources are needed for computation, where typically we would measure the resources in terms of time and space. Can we perform some task in a feasible number of steps? Can we perform some algorithm with only a limited memory? Does randomness help? Are there standard approaches to overcoming computational difficulty?

Table of Contents

Frontmatter

Background

Frontmatter
Chapter 1. Some Naive Set Theory
Abstract
This chapter gives meaning to the notion of size (cardinality) for infinite sets. We define countable and uncountable sets, and introduce Gödel numbering, coding, and diagonalization arguments. These ideas will be recycled throughout the book.
Rod Downey

Computability Theory

Frontmatter
Chapter 2. Regular Languages and Finite Automata
Abstract
We introduce the notion of a regular language, and show that regular languages are precisely those that are accepted by deterministic finite automata. We introduce nondeterminism, and prove that for automata, nondeterministic and deterministic machines have the same power, the trade-off being an exponential increase in the number of states. We finish with the Myhill-Nerode Theorem which shows how finite state is that same as having finite index for a certain canonical equivalence relation.
Rod Downey
Chapter 3. General Models of Computation
Abstract
We give some general models of computation, including Turing Machines, partial recursive functions, and register machines. We discuss the Church-Turing Thesis. We prove the existence of a universal Turing machine and discuss Kleene Normal Form. We also look at primitive recursion.
Rod Downey
Chapter 4. Undecidable Problems
Abstract
We prove a number of natural problems are undecidable. We do this by coding the halting problem into them. These problems include Conway’s generalization of the Collatz function, word problems in formal languages, the Entscheidungsproblem, word problems in semigroups and groups, and we finish with a proof of the undecidability of Hilbert’s 10th Problem for exponential Diophantine equations.
Rod Downey
Chapter 5. Deeper Computability
Abstract
In this Chapter, we will develop a number of more advanced tools we can use to tackle issues in computability theory. In particular, we will be able to deal with problems more complex than the halting problem, as delve more deeply into the fine structure of reducibilities and noncomputable sets. We introduce Turing reducibility. We prove the s-m-n theorem and recursion theorem. We will look at computable structure theory via computable linear orderings. We introduce the arithmetical hierarchy and show how definability aligns with computation. Finally we will look at constructions in the Turing degrees including the finite extension and finite injury methods, showing how Post’s Problem was solved.
Rod Downey

Computational Complexity Theory

Frontmatter
Chapter 6. Computational Complexity
Abstract
This chapter looks at the basics of computational complexity theory. We examine how to calibrate computation by measuring the amount of time and space a machine uses. We introduce polynomial time and polynomial space. We prove the hierarchy theorems and Blum's speedup theorem.
Rod Downey
Chapter 7. NP- and PSPACE-Completeness
Abstract
We introduce NP-completeness. We prove the Cook-Levin Theorem. Using it we prove many natural problems are NP-complete, and using similar ideas show QBF is PSPACE complete, and then show several natural problems are PSPACE complete. We prove Savitch’s Theorem showing that NPSPACE=PSPACE. We finish by looking at advice classes, BPP and randomization.
Rod Downey
Chapter 8. Some Structural Complexity
Abstract
We develop some general results on computational complexity. We show that normal methods which relativize are insufficient to decide many natural questions about complexity class separations, including P vs NP. We prove Ladner's Theorem showing that the polynomial time degrees are dense.
Rod Downey
Chapter 9. Parameterized Complexity
Abstract
We look at the basics of parameterized complexity. This is a method which seeks to find tractability by limiting some parameter in the input. We analyse methods for proving parameterized tractability and also give some basic results the completeness and hardness theory. We also look at limitations of the methods and XP-optimality. The latter gives methods for proving various algorithms are more or less optimal, subject to complexity considerations.
Rod Downey
Chapter 10. Other Approaches to Coping with Hardness∗
Abstract
We look at several other approaches to coping with intractability. They include approximation algorithms, PTAS’s, average case complexity, smoothed analysis, and generic case complexity. We look at both the positive techniques and the hardness theories.
Rod Downey

Selected Solutions to Exercises

Frontmatter
Chapter 11. Solutions
Abstract
To specify the periodic sequence, you only need to specify the finite subsequence which generates it. For eventually periodic, you'd need to specify the finite initial segment, and the finite periodic part.
Rod Downey
Backmatter
Metadata
Title
Computability and Complexity
Author
Rod Downey
Copyright Year
2024
Electronic ISBN
978-3-031-53744-8
Print ISBN
978-3-031-53743-1
DOI
https://doi.org/10.1007/978-3-031-53744-8

Premium Partner

    Image Credits