We will grade a subset of the assigned questions, to be determined after the deadline, so that we can provide better feedback on the graded questions.

For bonus questions, we will not provide any insight during office hours or Piazza, and we do not guarantee anything about the difficulty of these questions.

We strongly encourage you to typeset your solutions in LATEX.

If you collaborated with someone, you must state their name(s). You must write your own solution for all problems and may not look at any other student’s write-up.

0. If applicable, state the name(s) and uniqname(s) of your collaborator(s).

1. Properties of polytime mapping reductions.

(a) Show that A ≤p A for any language A.

(b) Prove the transitive property for polytime mapping reductions.  That is, prove that if A ≤p B and B ≤p C, then A ≤p C .

(c) Prove that if A ≤p B, then A ≤T B .

(d) Show that there exists languages A,B for which A ≤T  B but not A ≤p  B, where B is neither ∅ nor Σ* .

Hint : There exist languages known to not be in P. Some such languages are

Chess = {(C,n) : }

and

BoundedHalt = {(⟨M⟩,x,k) : }.

2.   (a) Show that the following language is NP-Hard:

k-#SAT = {(φ,k) : φ is a Boolean formula with ≥ k satisfying assignments} Alternate: Show that the following language is NP-Hard:

(b) Consider the following verifier for k-#SAT:

Does this verifier demonstrate that k-#SAT ∈ NP? Why or why not?

(c) Show an efficient algorithm that given a positive integer k, outputs a Boolean formula that has at least k satisfying assignments.

Hint : You cannot generate a formula that has O(k) variables, as its length would not be polynomial in the size of the input. (Why?)

3. Show that the language VertexCover = {(G,k) : G is an undirected graph that has a vertex cover of size equal to k} is NP-Hard by showing that Clique ≤p VertexCover.

4. Consider the language:

SubgraphIsomorphism = }

Recall that a subgraph G\ = (V\,E\ ) of G = (V,E) is a graph such that V\  ⊆ V and E\  ⊆ E .

A graph G1  is isomorphic to G2  if they differ only in how their vertices are labeled. In other words, we can convert G1  to G2 just by changing labels on the vertices.

Prove that SubgraphIsomorphism is NP-complete.

(a) Prove that SubgraphIsomorphism is in the class NP.

(b) Prove that SubgraphIsomorphism is NP-hard.