CS 555-3
Computability and Complexity
Catalog Description
Turing machines and other models of computation. Computable functions. Church's thesis. Solvable and unsolvable problems. Introduction to complexity theory including the classes P and NP. Polynomial time approximation algorithms for NP-complete problems.
Prerequisite:
CS 451.
Objectives
To study and understand the main results in the theory of computability. To appreciate how this theory serves as the underlying framework for the basic notions of "algorithm" and "effectively calculable function." To apply these concepts in classifying the complexity of algorithms and in establishing the intractability of a large class of problems.
Course Outline
| 1. | Classical Theory of Computation
Historical remarks on the concepts of "effectively calculable function," "decidable set," and "algorithm." Formal models of computation including the Turing machine. Partial recursive functions, primitive recursive functions, recursive sets and predicates. The relation between computable functions and partial recursive functions. Church's thesis. Halting problems. Recursively enumerable sets, recursively solvable and unsolvable decision problems. |
16 |
| 2. | Complexity Classification
Complexity classification. Examples of complexity measures based on tape usage and time. The general notion of a computational complexity measure. Speed-up theorems, complexity classes and applications. |
8 |
| 3. | Intractable Problems
Polynomial time and space. The classes P and NP. NP complete problems, PSPACE problems. Some provably intractable problems. Polynomial time approximation algorithms for intractable problems |
16 |
| Total | 40 | |