The difference hierarchy DiP 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 G2 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 DP is polynomial time reducible to Z.