Question

The difference hierarchy${\mathit{D}}_{\mathbf{i}}\mathit{P}$is defined recursively as

1. role="math" localid="1664206013824" ${\mathit{D}}_{\mathbf{1}}\mathit{P}\mathbf{\in }\mathit{N}\mathit{P}$and
2. ${\mathit{D}}_{\mathbf{i}}\mathit{P}\mathbf{=}\left\{A|A=B\backslash CforBinNPandCin{D}_{i-1}P\right\}\mathbf{.}$

(Here $\raisebox{1ex}{$\mathbf{B}$}\!\left/ \!\raisebox{-1ex}{$\mathbf{C}$}\right.\mathbf{=}\mathit{B}\mathbf{\cap }\overline{\mathbf{C}}$.) For example, a language in D2P is the difference of two NP languages. Sometimes ${\mathit{D}}_{\mathbf{2}}\mathit{P}$ is called DP (and may be written DP). Let $\mathit{Z}\mathbf{=}\left\{(G_1,k_1,G_2,k_2)|G_{1}hasa{k}_1-cliqueand{G}_{2}doesn\text{'}thavea{k}_2-clique\right\}$

.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.

Short answer

It is computable in polynomial time also $w\in L$, iff role="math" localid="1664206415899" $f\left(w\right)\in C$.Since $w\in L$, iff $w\in L_1$and $w\notin L_2$,iff $f_1\left(w\right)\in CLIQUE$and$f_2\left(w\right)\notin CLIQUE$ , if $f\left(w\right)\in C$ Polynomial time.

Step-by-step solution

Nondeterministic Time

In a nondeterministic turning machine, when the issue can be solved in polynomial time, it is allocated to the NP (nondeterministic time) class.

Explain the given information

Consider the difference hierarchy $D_{i}P$ is defined recursively as

a.${\mathrm{D}}_1\mathrm{P}\in \mathrm{NP}$and

b. $D_{i}P=\left\{A|A=B\backslash CforBinNPandCin{D}_{i-1}P\right\}.$

(Here $\raisebox{1ex}{$B$}\!\left/ \!\raisebox{-1ex}{$C$}\right.=B\cap \overline{C}$.) For example, a language in D2P is the difference of two NP languages. Sometimes $D_{2}P$is called DP (and may be written DP). Let$Z=\left\{(G_1,k_1,G_2,k_2)|G_{1}hasa{k}_1-cliqueand{G}_{2}doesn\text{'}thavea{k}_2-clique\right\}$

Show that Z is complete for DP 

Let $C_1=\left\{\left(G_1,k_1,G_2,k_2\right)|G_1\text{hasa}{k}_1-clique{G}_2\text{is} \text{any} \text{graphand}{k}_2⩾0\right\}$and $C_1=\left\{\left(G_1,k_1,G_2,k_2\right)|G_2\text{hasa}{k}_2-clique{G}_1\text{isanygraphand}{k}_1⩾0\right\}$

Both the language are NP complete.

So $C=C_1{C}_2$and so $C=DP$ .

Let us now demonstrate that C is DP-hard. Lets $L\in DP$. Consider the case $L=L_1{L}_2$such that $L_1{L}_2\in NP$ . There is polynomial time reduction f₁ and f₂ from L₁ and L₂ to respectively by the NP-compeleteness to the clique problem.

$f\left(w\right):=\left(f_1\right(w),f_2(w\left)\right)$

It is computable in polynomial time also $w\in L$iff role="math" localid="1664208080142" $f\left(w\right)\in C$since $w\in L$iff$w\in L_1$ and $w\notin L_2$,iff role="math" localid="1664208430444" $f_1\left(w\right)\in CLIQUE$and $f_2\left(w\right)\notin CLIQUE$, if $f\left(w\right)\in C$Polynomial time.

Therefore, Z is complete for DP.