Theory of computation notes

What is a decision Problem?

A problem that can be seen as a yes-no question denpendant on the input

What does it mean for a decision problem to be decidable?

It's decidable when it can be solved by an algorithm that stops on all inputs in a non-infinity amount of steps

What is the class P? What is the class NP?

Class P is constituted of numbers that are solvable in polynomial time, O(n^k) where k is constant, these problems are tractable

Class NP is the set of all decision problems. Polynomial time can also be defined as fast

What is the intuitive meaning of the "P versus NP" question?

In caveman terms, P is a set of relatively hard problems, NP the opposite so P = NP implies that hard problems actually have relatively easy solutions

If you resolve the P versus NP question, how much richer will you be?

One million dollars :O

Summary of Christos's lecture

Links

s1

s2

s3

s4