Show that the language MAX-CLIQUE from Problem 7.48 is in P^SAT.

Problem 7.48

The difference hierarchy D_iP is defined recursively as

a. D₁P = NP and

b. D_iP = {A| A = B \ C for B in NP and C in D_i−1P}.

(Here B \ C = B ∩ C.)

For example, a language in D2P is the difference of two NP languages. Sometimes D₂P is called DP (and may be written D^P). Let

Z = {〈G₁, k₁,G₂, k₂〉| G₁ has a k₁-clique and G₂ doesn’t have a k₂-clique}.

Show that Z is complete for DP. In other words, show that Z is in DP and every language in D^P is polynomial time reducible to Z.