# 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.