Languages

**wood** · 10-18-2003, 11:43 AM

Which of the following statements is (are) true?

I. There is a language L such that L is not recursive (L is undecidable), yet L and its complement are both recursively enumerable
II. There is a language L such that L is not recursive, yet L is recursively enumerable
III. Every language in NP is recursive.

(A) None
(B) II only
(C) I and II only
(D) II and III only
(E) I, II, and III

**ozgulker** · 10-18-2003, 01:55 PM

I. if L and its complement are both recursively enumerable, then L should be recursive. However it is stated that L is not recursive, therefore I is wrong.
II. Since recursive languages as a whole is a subset of REs, II is correct.
III. I am not very sure of it, but I believe it is true. There should be some sort
of TM even if it takes exponential time.

So with %50 percent guessing I say D. Am I lucky?

**wood** · 10-18-2003, 08:41 PM

Yes, you are ozgulker!

I was in doubt between (B) and (D), since I was not sure about III. Can someone elaborate on that one?

Wood

**rafi_dery** · 10-19-2003, 07:47 PM

about III:
If a language is in NP, it means there is a polynomial non-deterministic algorithm to check whever a word belongs to the language or not. We should not be confused about the non-determinism (the algorithm uses a coin. what is wrong with that?). Since there is an algorithm --> the problem is decidable (recursive).