Introduction

The Two Central Questions of the Course

What is theoretical computer science really about? At its heart, this course revolves around two fundamental questions about computation:

1. What are the absolute limits of what computers can do? This is the realm of Computability.

2. Of the problems we can solve, how efficiently can we solve them? This is the realm of Complexity.

NP-complete

Classes of Problems: P and NP

P (Polynomial Time)

The class of decision problems (problems with a “yes” or “no” answer) that can be solved by a deterministic algorithm in polynomial time.

Problems in P are considered efficiently solvable.

Example: The Eulerian Tour problem belongs to the class P.

---

NP (Nondeterministic Polynomial Time)

The class of decision problems for which a “yes” answer can be verified in polynomial time, given a suitable certificate or proof.

More formally, a problem is in NP if there exists a nondeterministic algorithm that can solve it in polynomial time.

A nondeterministic algorithm can be thought of as making “lucky guesses” that always lead to a solution if one exists.

NP-complete

a problem $\Pi \in NP$ is NP-complete if $\Pi \in P⟹P=NP$

Link to original