Description
1. [12 marks]
(a) [4 marks] Let f(n) = 4n
2 − 30n + 6. Prove that f(n) ∈ O(n
2
). In your proof, give explicit values for c
and n0.
(b) [4 marks] Let f(n) = n
999 and g(n) = (√
log n)
√
log n.
Precisely one of the following two claims is true:
f(n) ∈ O(g(n)), g(n) ∈ O(f(n)). Prove whichever one is true. In your proof, give explicit values for c
and n0. (Hint: Note that an arbitrary function f(n) can be rewritten as 2
log2
(f(n)).)
(c) [4 marks] This question tests an important subtlety in the definition of “polynomial-time”. One of the most
famous open problems in classical complexity theory is whether the problem of factoring a given integer
N into its prime factors is solvable in polynomial time on a classical computer1
. Given positive integer N
as input, why is the following naive approach to the factoring problem not polynomial-time?
1: Set m := 2.
2: Set S := ∅ for S a multi-set.
3: while m ≤ N do
4: if m divides N then
5: Set S ∪ {m}.
6: Set N = N/m.
7: else
8: Set m = m + 1.
9: end if
10: end while
11: Return the set S of divisors found.
2. [6 marks] Let co-NP denote the complement of NP. In other words, intuitively, co-NP is the class of languages
L for which if input x 6∈ L, then there is an efficiently verifiable proof of this fact, and if x ∈ L, then no proof
can cause the verifier to accept.
Prove that if P = NP, then NP is closed under complement, i.e. NP = co-NP. How can closure of NP under
complement hence potentially be used to resolve the P vs NP question?
3. [10 marks] In class, we introduced the language
CLIQUE = {hG, ki | G is a graph containing a clique of size at least k}.
1
In fact, many popular cryptosystems are based on the assumption that this problem is not efficiently solvable. Recall from class, however, that
in 1994 it was shown by Peter Shor that quantum computers can efficiently solve this problem!
1
Consider now two further languages:
INDEPENDENT-SET = {hG, ki | G is a graph containing an independent set of size at least k}
VERTEX-COVER = {hG, ki | G is a graph containing a vertex cover of size at most k}.
Here, for graph G = (V, E), an independent set S ⊆ V satisfies the property that for any pair of vertices
u, v ∈ S, (u, v) 6∈ E. A vertex cover S ⊆ V satisfies the property that for any edge (u, v) ∈ E, at least one of
u or v must be in S.
(a) [4 marks] Prove that CLIQUE ≤p INDEPENDENT-SET. (Hint: Given a graph G, think about its complement. Google “complement graph” for a definition.)
(b) [6 marks] Prove that INDEPENDENT-SET ≤p VERTEX-COVER.
4. [8 marks] Let CNFk = {hφi | φ is a satisfiable CNF-formula where each variable appears in at most k places}.
Show that CNF3 is NP-complete. (Hint: Suppose a variable x appears (say) twice. Replace the first and second
occurrences of x with new distinct variables y1 and y2, respectively. Next, add clauses to ensure that y1 = y2.
To do this in CNF form, recall that y1 = y2 is logically equivalent to (y1 =⇒ y2) ∧ (y2 =⇒ y1), and that
(a =⇒ b) can be rewritten as (a ∨ ¯b) ∧ (
¯b ∨ a). How can this trick be applied more generally when x appears
m > 2 times?)
5. [8 marks] It is possible for a problem to be NP-hard without actually being in NP itself. For example, the halting
problem from class is clearly not in NP, since it is undecidable. However, in this question, you will show that
the language HALT = {hM, xi | M is a TM which halts on input x} is NP-hard. Is the halting problem hence
NP-complete?
6. [8 marks] In class, we have focused on decision problems, i.e. deciding whether x ∈ L or not. For example,
given a 3-CNF formula φ, recall that the decision problem 3SAT asks whether φ is satisfiable or not. In practice,
however, we may not just want a YES or NO answer, but also an actual assignment which satisfies φ whenever
φ is satisfiable.
It turns out that in certain settings, being able to solve the decision version of the problem (e.g.
3SAT) in polynomial time implies we can also solve the search version (e.g. find the satisfying assignment
itself) in polynomial time. Problems satisfying this property are called self-reducible.
Your task is as follows: Show that 3SAT is self-reducible. In other words, given any 3-CNF formula φ and a
polynomial-time black-box M for determining if φ is satisfiable, show how to find a satisfying assignment for
φ in polynomial time. You may assume that M is able to decide all CNF formulae with at most 3 variables per
clause.
2