Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework 5 – Deadline June 28, 11:59 pm

June 22, 2023

Instructions:  The goal of this course is to strive for mathematical clarity in computation. In that spirit, please make sure your answers are clear, concise and rigorous.  The onus for all three is on you.  Use a word processor to type your answers (preferably Latex).

You will be allowed to collaborate in groups of two.  But you must write your solutions individually.

1.  [10 points] Let L be a non-trivial language – i.e., L  Φ and L  {0, 1}* . Prove that if P = NP, then 3 − SAT ≤p  L.

2.   [10 points] For undirected graphs G1   =  (V1 ,E1 ) and G2   =  (V2 ,E2 ), we say that there is a homomorphism from G1  to G2 , if there is a map f : V1  → V2 such that (a) f is one-one and (b) (u,v) ∈ E1  if and only if (f(u),f(v)) ∈ E2 . Let L = {⟨G1 ,G2 ⟩ : there is a homomorphism from G1  to G2 } . Show that L is NP-complete.