0
$\begingroup$

How to prove that diagonal language is NP hard ? Any pointers in the direction would help. I am aware of this question but all the answer gives is a definition of reduction.

Edit : Diagonal-language contains all strings X s.t. Mx(x) = 0 where Mx is the turing machine whose string encoding is given by x.

$\endgroup$
  • 3
    $\begingroup$ You should give a formal definition of the "diagonal language" in your post. $\endgroup$ – fade2black Dec 25 '17 at 7:20
  • $\begingroup$ @fade2black I added the definition. Does that suffice ? $\endgroup$ – s1998 Dec 26 '17 at 14:04
  • $\begingroup$ See this post about NP-hardness of the halting problem. Almost the same proof works for your case, can you tell why? $\endgroup$ – Ariel Dec 26 '17 at 14:09
  • $\begingroup$ @Ariel I get it. "Given a SAT formula φ, construct a Turing machine M which iterates over all truth assignments for φ, and so determines if φ is satisfiable or not. If it is, it halts. If it isn't, it doesn't halt (gets into an infinite loop)." In this case the reduction machine will give code of M. Right ? $\endgroup$ – s1998 Dec 28 '17 at 17:32
  • $\begingroup$ I found out later that [this] (cs.stackexchange.com/questions/81141/…) link can help too. $\endgroup$ – s1998 Dec 28 '17 at 17:35