Suppose there are three languages (i.e.. problems), of which we know the followi

Question

Suppose there are three languages (i.e.. problems), of which we know the following: 1. LI ism P. 2. L2 is NP-complete. 3. L3 is not in NP. Suppose also that we do not know anything about the resolution of the "P vs. NP" question; for example, we do not know definitely whether P=NP. Classify each of the following languages as (a) Definitely in P. (b) Definitely in NP (but perhaps not in P and perhaps not NP-complete) (c) Definitely NP-complete (d) Definitely not in NP: L1 [union] L2. L1 intersection L2. L2cL3. where c is a symbol not in the alphabet of L2 or L3 (i.e.. the marked concatenation of L2 and L3. where there is a unique marker symbol between the strings from L2 and L3). The complement of L3. Based on your analysis, pick the correct, definitely true statement from the list below. a) L1 [union] L2 is definitely not in NP. b) L2cL3 is definitely not in NP. c) L1 intersection L2 is definitely not in NP. d) The complement of L3 is definitely not in NP.

Explanation / Answer

The complement of L3 is definitely not in NP is the correct statement.

Why because, Let consider L = L2cL3.

Suppose L had an NP-recognizer. Let x be some string in L2 (since L2 is NP-complete, and we do not know that P = NP, we can be sure L2 is not empty, so x exists).

Then there is a nondeterministic polynomial-time algorithm for L3 that works as follows.
Take input w, and test it for membership in L3 by feeding xcw to the NP-recognizer for L.
Respond exactly as this recognizer responds.

Since we know x is in L2, the recognizer for L accepts xcw if and only if w is in L3.
We now have an NP-recognizer for L3, but we were told that L3 is not in NP.

Thus,
our assumption that L is in NP must be false. Last, let L be the complement of L3.

If L is in P, then the complement of L, which is L3, is also in P.

But we know L3 is not even in NP. We do not even know that L is in NP; for example, L3 could be an undecidable problem.

On the other hand, L could be NP-complete.

For example, the complement of the problem SAT is not known to be in NP. But it is possible that L3 is the
complement of SAT and therefore L = SAT, a known NP-complete problem

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.