Reference no: EM132835668

Question 1. Prove that SAP ≤^P_m TAUT and TQBF₂ ≤^P_m TAUT ≤^P_m  => means polynomial time reducible

Question 2. a) Prove a Hamilton cycle decision problem has a polynomial time algorithm

b) Prove Hamilton cycle search problem has a polynomial time algorithm.

Question 3. Let X ξ Y be 2 languages, X-Y = X ∩ B^C = {z ∈{0, 1} *|x ∈ x ξ z ∈/ Y}

X - Y => Difference of X and Y

DP = Complexity class DP = {x - Y| x, y ∈ NP}
This can be rewritten as DP = {Xny | X∈NP, Y∈CoNP}

a) Show that UNIQUE - SAT ∈ DP; UNIQUE - SAT { Φ | Φ has exactly one satisfying Assignment}

b) Show that EXACT - CLIQUE ∈ DP; EXACT -CLIQUE = {G,B> | w(G) = k}
G = graph w(g) = sing of biggest clique in G

Prove that NP U CONP ⊆ DP ⊆ Σ^P_z nΠ^P₂

Prove That if NP = DP, Then NP = PH

Question 4. A function that can be computable in a polynomial time is known as preference function.

Let z : {0, 1} ^* × {0, 1} ^* → {0, 1} ^*.

For all pair of strings a,b∈ {0, 1} ^* , z(a, b) ∈ {a, b}. This means z outputs one of its two inputs, the string it "prefers" out of the two.

Let X ⊆ {0, 1} ∗ .z is known as a good preference function for X if for all z, b ∈ {0, 1} ^* , a ∈ X or b ∈ X ⇒ z(a, b) ∈ X.

This means that z always prefers strings that belong to X.

Question: Having all of this information, (a) prove that SAT has a good preference function.

(B) Prove that P=NP

Attachment:- Problems.rar