This question already has an answer here:

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.


marked as duplicate by fade2black, Yuval Filmus complexity-theory Dec 26 '17 at 15:08

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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