Theoretical CS

4.4 Computational Complexity

In the previous unit, we mentioned the idea that a Turing Machine can be used to prove theories about the capabilities of a computer. We will formalize this concept and study examples of such proofs.

Halting Problem

The Halting Problem is a classic example of a computational question: given a program and input, can a computer determine whether that program will halt or run forever without running the program? We will prove the answer using a Turing Machine.

P versus NP

Another example of a major problem in computer science is the P vs NP problem. We will use Turing Machines to examine the idea of polynomial and nondeterministic polynomial, which is necessary to understand the problem: can algorithms that can be verified in polynomial time also be solved in polynomial time? This problem is still unsolved!

We will study several examples of NP problems, and prove that they are in fact NP.

<< 4.3 Turing Machines 4.5 Lab 4 >>