GATE CSE 1995 | Question: 11

Question

Let $L$ be a language over $\Sigma$ i.e., $L\subseteq \Sigma^*$. Suppose $L$ satisfies the two conditions given below.

1. $L$ is in NP and

2. For every $n$, there is exactly one string of length $n$ that belongs to $L$.

      Let $L^c$ be the complement of $L$ over $\Sigma^*$. Show that $L^c$ is also in NP.

Comments

https://www.youtube.com/watch?v=YX40hbAHx3s&t=28s

This video is explaining the hierarchy of decidable problems. Yes, there exist some problems which are decidable but not NP. NP means, given a solution of the problem,we can VERIFY it in polynomial time.

Now there are some problems for which verifying a given solution in polynomial time is also not possible, ex - given a instance of a chess game whether the next move is the best move or not. It is decidable but not NP.

Answer 1

Since $L$ is in NP it is decidable (recursive) and so is its complement $L^c$. Now, $L^c$ may or may not be in NP. But we are given that for any string length $n$, exactly one string belong to $L$, which means for any string length all but one string belong to $L^c$. 

Now, definition of NP says that all instances of the problem can be solved in polynomial time using a nondeterministic TM. So, given an instance of $\langle L^c, x\rangle$, we non-deterministically take all words of length $n$, where $n$ is the length of $w$, and see if it is in $L$. As soon as we get the word (such a word is sure to exist as exactly one word of length $n$ belong to $L$), we see if this word is same as $x$. If it is not same (and only if it is not same), $x \in L^c$ and we get this answer in polynomial time making $L^c$ an NP problem. 

Comments

Can NO instances can be solved in polynomial time in np?????

---

@Subbu. Solving a problem means for both yes/no cases. The given statement in answer was not correct – just fixed now.

---

@Jaswalkashish06

that’s the alternative defination.

Answer 2

If L is a language in NP then L is Turing decidable. So, complement of L is also Turing decidable but not necessarily in NP. To prove it is NP use (ii).

Comments

Complement is Turing decidable. But need not be NP. To prove complement is in NP, we need to make use of second condition.

---

How to prove it is in NP?

---

how to use ii to prove its complement in np???