# EQtm is not mapping reducible to its complement

This is a problem from Sipser's book (marked with an asterisk).

$EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$

We know that neither $EQ_{TM}$ nor $\overline{EQ_{TM}}$ are recognizable so unsure how to go about proving there can't be a mapping reduction from one to the other.

Any hints?

• Where exactly did you get stuck? What are your thoughts? – vonbrand Jan 29 '16 at 17:12
• First I realized that it's not useful to use the reduction from any other language to either $EQ_{TM}$ or $\overline{EQ_{TM}}$ and then look for contradiction (the language would then be recognizable or decidable) - because we know they are not recognizable. – user1255841 Jan 29 '16 at 17:16
• Then I tried to use the fact that I have a 1-to-1 map from $<M_1, M_2>$ to $<N_1,N_2>$ where $L(M_1) = L(M_2)$ and $L(N_1) \ne L(N_2)$ . Now I am trying to find a language that I can construct a TM to recognize using this map - and so far not finding any – user1255841 Jan 29 '16 at 17:19

Your language is $\Pi_2$-complete: it can be written as a $\Pi_2$ formula, and TOT can be reduced to it. The complement is therefore $\Sigma_2$-complete. No computable reductions can exist between $\Pi_2$-complete and $\Sigma_2$-complete sets (why?).

• Can you clarify what Pi_2 - complete means as well as what TOT refers to and what Sigma_2 complete means? – NateSHolland Feb 6 '16 at 15:06
• These are levels of the polynomial hierarchy, explained for example on Wikipedia. TOT is the language of all Turing machines that halt on all inputs. – Yuval Filmus Feb 6 '16 at 16:34
• I see, and so the inequality is NP complete and checking equality is co-NP complete and we can't reduce between the two? – NateSHolland Feb 6 '16 at 16:37
• It's not known to be in NP. In fact, it's conjectured to be in neither NP nor coNP. It's both NP-hard and coNP-hard, though. – Yuval Filmus Feb 6 '16 at 16:45
• Which one is NP-hard and which one is CoNP-hard? – NateSHolland Feb 6 '16 at 16:52

If there were a reduction $f$ from $EQ_\mathsf{TM}$ to $\overline{EQ_\mathsf{TM}}$, then it would be a computable function satisfying that

$$f(\langle M_1,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

where $L(M_1) = L(M_2) \iff L(M'_1) \neq L(M'_2)$.

We would then also have computable functions $f_1, f_2 : \Sigma^* \rightarrow \Sigma$ defined by

$$f_1((\langle M_1 \rangle, \langle M_2 \rangle)) = \langle M'_1 \rangle \text{ if } f(\langle M_1,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

$$f_2(\langle M_1 \rangle, \langle M_2 \rangle)) = \langle M'_2 \rangle \text{ if } f(\langle M_1,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

But then by the first recursion theorem, we would have "curried" versions of these for any given $M$:

$$f^M_1(\langle M_2 \rangle) = \langle M'_1 \rangle \text{ if } f(\langle M,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

$$f^M_2(\langle M_1 \rangle) = \langle M'_2 \rangle \text{ if } f(\langle M_1,M_2 \rangle) = \langle M'_1, M'_2 \rangle$$

By the fixed-point theorem, there must then be a machine $F$ such that

$$f^M_1(\langle F \rangle) = \langle F' \rangle$$

where $L(F') = L(F)$ and a machine $G$ such that

$$f^M_2(\langle G \rangle) = \langle G' \rangle$$

and $L(G') = L(G)$.

But then we get that $f(\langle F, G \rangle) = \langle f^F_1(\langle G \rangle), f^G_2(\langle F \rangle) \rangle = (\langle F', G' \rangle)$. Clearly we do not have that $L(F) = L(G) \iff L(F') \neq L(G')$.

We have thus reached a contradiction, using only the assumption that $f$ existed.