Question 10243 – Theory-of-Computation

Let L be a language over ∑ i.e., *L ≤ ∑ . Suppose L satisfies the two conditions given below
(i) L is in NP and
(ii) For every n, there is exactly one string of length n that belongs to L.
Let L^c be the complement of L over ∑*. Show that L^c is also in NP.

Correct Answer: A