Week One

Question 1

What is Big-O Notation?

Answer 1

Upper Bound

f(n) = O(g(n))

iff c, n0 such that whenever n >= n0,
we have f(n) <= cg(n)

Question 2

What is Big-Ω Notation?

Answer 2

Lower Bound

f(n) = Ω(g(n))

iff g(n) = O(f(n))

Question 3

What is Big-θ Notation?

Answer 3

Tight Bound

f(n) = θ(g(n))

iff f(n) = O(g(n)) and g(n) = O(f(n))

Question 4

Explain the SAT problem

Answer 4

Prop Vars: Prop = {p0, p1, …}
Formulas: A, B ::= pi | ¬A | A v B | A ^ B

Assignments: α : Prop -> {0, 1}
SAT is the set of formulas A for which there is α(A) = 1.

Question 5

What is the definition of decidability?

Answer 5

An algorithm A(x) decides a predicate/language L⊆{0, 1}* in time O(f(n)) if, for each instance x ∈ {0, 1}*, A(x) terminates after O(f(|x|)) basic steps of computation and accepts iff x ∈ L.

Question 6

What is the definition of P?

Answer 6

P is the set of L ⊆ {0, 1}* such that there is some polynomial p(n) and an algorithm A(x) deciding L in O(p(n)) steps.

Question 7

What is the definition of NP?

Answer 7

NP is the set of languages L ⊆ {0, 1}* for which there is a
polynomial-time algorithm A(x, y) and a polynomial p(n) such that:

x ∈ L ⇐⇒ ∃y.(|y| < p(|x|) and A(x, y) accepts)

For a given x ∈ L, we may call such a witness y the certificate (guessed) of acceptance.
The algorithm A(x, y) is the verifier.

Question 8

What is the definition of a polynomial-time reduction?

Answer 8

A polynomial-time reduction from L to L′ is a function
f : {0, 1}* → {0, 1}* such that:

• f is polynomial-time, i.e. we can compute f (x) in a number of steps polynomial in |x|.
• x ∈ L ⇐⇒ f (x) ∈ L′.

Question 9

What is the definition of NP-hardness?

Answer 9

L ⊆ {0, 1}* is NP-hard if for every L′ ∈ NP we have L′ ≤p L.

If, furthermore, L ∈ NP, then we say L is NP-complete.

Question 10

What are the NP bounding principles?

Answer 10

if L ∈ NP and L′ ≤p L then L′ ∈ NP.

if L is NP-hard and L ≤p L′ then L′ is NP-hard.