Lectures 10 and 11

Today’s topic: P vs NP

This will be a not so formal introduction to P and NP. Every computer scientist should know something about NP complete problems. If you know that a problem is NP complete, then you know that it is very hard to find an optimal solution.

• The definition of P and NP
• The definition of Reduction and NP Hardness
• NP Completeness
• Some NP Complete Problems.
• What now? What courses should I take to learn more about algorithms and optimisation?

This material is examined.

Links to Slides and other material.

These lectures will given by Pierre Flener.

The slides for the lecture can be found here

Reading Guide

• All of Chapter 34 of CLRS3 or CLRS4.

What should I know by the end of this set of lecture?

• The definition of NP? What has guessing a solution got to do with complexity?
• How do reductions work?
• What is a complete problem for a complexity class?
• You should know some NP-complete problems and have enough idea about how reductions work so that you can decide if your problem is NP-complete or not.