CS370 - Computation and Complexity

CS370 Homepage.

Course Outline

Computational complexity theory (CCT) is an extension to the theory of computation, and accordingly this course begins with some background information on incompleteness, Turing's computable numbers, algorithmic decidability and uncomputability, several models of computation and the reducibility between unrestricted models.

This leads us on to intractability, machine-independent complexity, measures of complexity and asymptotic analysis.

From here we define some complexity classes, define intra-class reductions, develop several techniques for the complexity analysis (best, worst, average case) of algorithms, and prove that certain algorithms are optimal for a given model of computation and given complexity measures.

The concept of nondeterminism allows us to develop a richer complexity class structure (including the class NP, NP-completeness, NP-hardness), and we prove a solution's membership of these classes.

A detailed outline of the course is given below. A subset of these topics will be given this year. Possibilities for the final section of the course include parallel complexity theory, probabilistic algorithms (in more detail), Kolmogorov complexity, and algorithmic complexity/entropy.

Detailed Outline

Unit 0 Prehistory

Calculation, The first symbol processing, Three elements of computation

Unit 1 Introduction to CCT

Origins and goals of the theory, Models of computation, Simple example, Growth rates & measures of complexity, Tractability, Intractability, Example: the rook path chessboard problem, "Lifetime of the universe" problems, Travelling salesman problem, Categorisation of all problems faced by humans, Course outline

Unit 2 Historical Foundations

Hilbert, Russell, Gödel, Incompleteness theorem, Entscheidungsproblem (decidability), Turing's solution, Mathematical machines, pre-1935 Babbage, Boole, Turing's background

Unit 3 Computability I - Computable Numbers

Summary of Turing's "On computable numbers...", Description of Turing's machine, Defining computability, The computable numbers

Unit 4 Mathematical Preliminaries I - Sets

Elementary logic/set theory, Relations and functions, Cardinality and infinite sets, Proof techniques, Graphs, Alphabets, words and languages (definitions)

Unit 5 Computability II - Universal Computation

Defining uncomputability, Apparent paradox of uncomputable numbers, The halting problem, An answer to Hilbert's Entscheidungsproblem, The Universal machine, Church and the lambda calculus, Kleene and recursion theory, Effective calculability, Church's thesis, Unrestricted models of computation, Predicate calculus & the lambda calculus

Unit 6 Mathematical Preliminaries II - Asymptotic Notation

Asymptotic notation (limits at infinity), Big-O, Logarithms, Comparison of common growth rates, Little-o, Omega, and Sigma, Flooring and ceiling functions

Unit 7 Models of Computation I - TMs & RAMs

Why we use simple/abstract/restricted models, The k-tape deterministic (quintuple) Turing machine, Acceptor machines and transducer machines, Oracle Turing machines, RAMs, Logic circuits, finite automata, cellular automata

Unit 8 Models of Computation II - Machine Models

Machine-independent complexity, The Invariance Thesis and 'reasonable' machines, The first and second machine classes, General formulation of a machine model, Simulations: k-tape TM to 1-tape TM, k-tape TM to 2-tape TM, k-tape TM to RAM, RAM to k-tape TM, Performance measures of above simulations

Unit 9 Algorithmic Decidability

Decidability: what you know already, Partial recursive functions & recursive functions, Church's thesis & recursive functions, Recursive languages, acceptability and decidability, The existence of non-recursive languages, Undecidable properties of languages, How intuitive is the halting problem?, The tiling problem is undecidable, Reducibility between languages, Other undecidable problems

Unit 10 Measures of Complexity

Magnitude of a computation, Polynomial algorithms, Static and dynamic complexity measures, What defines a model-independent dynamic measure, Uniform and logarithmic cost measurement, TM time- and space-complexity, Interdependence of time & space in TMs

Unit 11 Complexity Classes - Deterministic Machines

Classes of languages: DSPACE, DTIME, PTIME, PSPACE, LOGSPACE, EXPTIME, EXPSPACE, Complexity of functions, Comparing classes: reductions, Polynomial reductions and class membership, Comparing classes: subroutines and oracles, Hardness and completeness

Unit 12 Space and Time

Linear speed-up theorem, Space & time of arbitrary functions, Space-time trade-offs, ‘Strong’ speed-up theorem, Upper and lower bounds

Unit 13 Introductory Algorithm Analysis (this year: searching)

Comparison-based model of computation, The reduction strategy, Recurrences, Linear search, Substitute and guess, Guess and test, Lower bound on worst cost - optimal worst cost, Average costing, Lower bound on average cost - optimal average cost, Jump search - worst cost, Optimal jump size by differentiation, Square root search, The balance strategy, Binary search, Deriving the worst cost recurrence, "3x+1" problem, Solving the recurrence - simplified solution, Solving the recurrence - strict solution, Decision trees, Optimal worst cost, Binary search has optimal worst cost, Average cost - simplified solution, Average cost - strict solution, Cases for a different search technique, Randomised linear search, Searching linked lists, Interpolation search, Hashing

Unit 14 The class PTIME

The significance of P, Algorithms in P, Arithmetic operations as a measure of complexity, Determining membership of P, Rules of thumb, Simulation & Reduction, The Euclidian algorithm for hcd, Inefficient algorithms, The shortest path problem, Polynomial-time intractable problems

Unit 15 Nondeterminism

Where are the tractable problems?, A new class of problems, Verifiable in polynomial time, Analysing correctness proofs, Bounded and unbounded nondeterminism, Nondeterministic TMs

Unit 16 Problems on the Border

Edge cover and node cover, Euler cycle and Hamiltonian cycle, 2-SAT and 3-SAT, Feedback edge and feedback arc sets, Linear and quadratic Diophantine equations

Unit 17 Nondeterministic Algorithms

Fully time-constructable functions, Well-computable functions, Witnesses, Savitch's Theorem, Nondeterministic complexity classes, Languages in NP, Complement of NP problems, The harder NP problems, Search problems and optimisation problems in NP

Unit 18 NP-completeness

Recap: Reductions and completeness, Cook-Levin Theorem, Further NP-c problems, Hitting set, Covering, k-partition and partition, Subset sum, Sum partition, NP MINUS P = ?, NP MINUS P MINUS NP-c = ?

Units 19-21 To be decided


NUIM Logo