We know from ex 6 that HTM is NP-HARD, and we know there is a reduction from HTM to ATM (we've never showed it, but we said there is).

Does the above and the fact that ATM is not in NP (since shes not in R) say that ATM is NP-HARD?

And if we show a reduction (mapping or poli?) from Atm to L, and we know that Atm is NP-hard, does it say that L is also NP-Hard if L is not in R and thus not in NP?

Im asking this in order to know if I can use it in exam from 2008 semester b moed a, when we asked to prove or disprove that L is in NP-HARD when

L is a lenguage of TM that their language is in C when C is not trivial.

We know from Rice that the language is not in R.

Is that another way of showing memberhod in NP-Hard besides reductions from problems in NPC?

First, if the reduction from Htm to Atm was not shown (wasn't it?) then it is only because is is so easy, try it.

Secondly, $A \leq_p B$ and $B \leq_m C$ does not entail $A \leq_p C$ (think of A and B as NP-complete problems and C as a known poli problem and you will understand why) and so your reasoning fails. But - indeed Atm is NP-hard by a proof very similar to the one given in ex. 6.

And if you show a poly reduction from any NP-hard problem to L, then L is also NP-hard.

I am not sure I got what you asked about the 2008 question, but you can ask again if this fails to help you.

הסיבה שקיימת רדוקצית מיפוי מבעיה השייכת ל

NP-complete

לבעיה פולינומיאלית היא שאפשר להמיר מ"ט לא דטרמינסטית המכריעה שפה מסויימת למ"ט דטרמינסטית המכריעה את אותה השפה?

ולכן זה אומר שלא קיימת רדוקציה פולינומיאלית כזו למשל כמו בדוגמה

A<pC?

תודה.

There is a mapping reduction between any two problems (except the empty set and Sigma star) in R. Since every

NPC problem satisfies the above (as NP is a subset of R) there is a mapping reduction from any NPC problem to

any non trivial problem in P.