in question 1 is it right UndirectedCycledHamiltonianPath <=p K-key ?

in question 2 why L in P ?

1) It has to be, if k-key is NPC, but what is the actual reduction you are suggesting?

2) I am not sure that is what they had in mind, but if you take x=y, you can always accept.

In question 2 section b:

Is there x and y s.t <M,x,y> isn't in L.

Isn't that equal to the question :is there x and y s.t <M,x,y> is in L-Co .

If its true, how its possible for L to be in p and L-Co outside RE ?

Can I prove the second section this way?:

Informally, this problem is equivalent to the problem:

Having a TM M, can we know weather it creates the EMPTY or the ALL-WORDS language?

Due to Rice's theorem this is a property of language, thus is undecidable, and belongs to RE\R.

On the other hand, due to Rice's theorem, the complement of this problem belongs to RE\R as well, thus the original problem belongs to R.

Is it right that this is a non trivial property of languages?

Thank you.

You are right in your observation of C to L-bar, but Rice tells you it is outside of R, not necessarily that it is in RE.

Your negation is wrong. It should be "for all" instead of "is there", and then your argument will not hold.

Omer's beginning is correct - it is indeed equivalent to checking whether L(M) is not EMPTY or ALL-WORDS.

To show that it is not in RE, try a reduction from A_TM_epsilon-bar, f(<M>)=<M'>, where M' on input x:

- If x = 1, accept.

- Run M on epslion.

- If M halts, accept.

Than, if M does not halt on epsilon, L(M')={1} which is neither EMPTY nor ALL-WORDS.

If M does halt on epsilon, L(M') = ALL-WORDS.