1. Good post? |
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

2. Good post? |
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?

3. Good post? |
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

4. Good post? |
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).

5. Good post? |
Thanks Rafi!!

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

SEO by vBSEO ©2010, Crawlability, Inc.