Theory-of-Computation
February 13, 2024
Question 10563 – Theory-of-Computation
February 13, 2024
Theory-of-Computation
February 13, 2024
Question 10563 – Theory-of-Computation
February 13, 2024

Theory-of-Computation

Question 12

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 Lc be the complement of L over ∑*. Show that Lc is also in NP.

A
Theory Explanation.
Correct Answer: A

Leave a Reply

Your email address will not be published. Required fields are marked *

error: <b>Alert: </b>Content selection is disabled!!