Prove that an oracle C exists for which${\mathrm{NP}}^{\mathrm{c}}\ne {\mathrm{coNP}}^{\mathrm{c}}$ .

We know that an oracle A exists such that $P^A\ne N{P}^A$and $L_A\notin P^A$then, for a given oracle A, $L_A$may be defined as:$L_A=\text{{}w:\left|w\right|=\left|x\right|$ for some$x\in A\text{}}$

So, it is clear that$L_A$ is in then it has to be proven that$L_A\notin coN{P}^A$

For this, first of all A is constructed. Now consider${\mathrm{M}}_1,{\mathrm{M}}_2\dots$as a list of all nondeterministic polytime oracle TMs, instead of all deterministic polytime oracle TMs.

For stage ‘i’ , choose ‘n’ and run $M_i$in input .

• If there does not exist any computation and if data-custom-editor="chemistry" $M_i$does not accept $1^n$,then $M_i$is forced to make a mistake. It is performed because ‘A’ can be maintained permanently that contains no string of length ‘n ‘. Then,$1^n\in {\overline{L}}_A$, but $M_i$does not accept.

• Therefore, there will be a string ‘x’ of length ‘n’ which the above computation does not query. It specifies that this string ‘x’ is in ‘A’ and no other string of length ‘n’ is in ‘A’.

• $M_i$Still has the same accepting computation on input $1^n\in {\overline{L}}_A$. Thus, makes a mistake in this case also.

So, from the above explanation, it can be concluded that an oracle C exists for which $N{P}^c\ne coN{P}^c$.