-2
$\begingroup$

Let L be a language over Σ i.e., $L\subseteq Σ^∗$. 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 $Σ^∗$.

Show that $L^c$ is also in NP.


My attempt:

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 we have to use (ii).

I don't know how to prove it is NP using (ii).

Can you explain it in a formal way, please?


This question is from competitive exam GATE. It's also been posted on Stackoverflow.

$\endgroup$
  • 1
    $\begingroup$ Well, what have you tried and where did you get stuck? $\endgroup$ – Raphael Sep 17 '15 at 15:12
  • 1
    $\begingroup$ If you already know that it's previously been posted on Stack Overflow, you shouldn't re-post it here, as posting the same question on multiple sites violates Stack Exchange rules. Once you have enough reputation, you can always put a bounty on that other question. That said, why do you think it's the same question as the one on Stack Overflow? That one says the number of words of length $n$ is $n$; this one says the number is $1$. Sounds different to me... $\endgroup$ – D.W. Sep 17 '15 at 18:53
  • 1
    $\begingroup$ We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and where specifically you got stuck. If you haven't made it that far, you should spend more time trying or studying concepts before asking. It will definitely draw more answers to your post. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – D.W. Sep 17 '15 at 18:55
  • $\begingroup$ Respected @D.W. , sir , Thanks to you .When I google it , I got at SO but I was unable to comment etc . since I have low reputation till now . Any way ,both of you are awesome sir to me , Thank you again , I will try always from next time . $\endgroup$ – 1 0 Sep 18 '15 at 5:57
4
$\begingroup$

Consider the complement of $L$, which satisfies the following property: for every $n$, there is exactly one string of length $n$ that is not in $L^c$.

In order to show that $L^c$ is NP, we show a polynomial time verifier for it. The verifier gets as input $x\in \Sigma^*$, and a witness $y,z$ such that $|y|=|x|$, $y\notin L^c$, and $z$ is a witness to the membership of $y$ in $L$. Now, the verifier first checks that $y\in L$ using the witness $z$, and then verifies that $y\neq z$.

If the verification succeeded, then $y\in L$, so $x\notin L$, so $x\in L^c$. Conversely, if $x\in L^c$, there must exists such a $y$.

$\endgroup$
  • $\begingroup$ How we can to find for every n, there is exactly one string of length n that belongs to L. (L is in NP ?) , why not exponential time , I got your solution , but , still , I didn't get question ? Please any comment . $\endgroup$ – 1 0 Sep 18 '15 at 6:30
  • $\begingroup$ Not sure I understand your question... Anyway, the fact that there is exactly one string of length $n$ in $L$ is an assumption, not something we need to find or verify. $\endgroup$ – Shaull Sep 18 '15 at 6:58
  • $\begingroup$ Interesting! Can this proof be adapted to show that if for some $L\in NP$, for every $n$, there are exactly $p(n)$ many $x\in L$ with $p(n)$ some polynomial, then $L\in co-NP$? The witness is all the $x\in L$ of length $n$, the verifier checks that there are exactly $n$, and the rest is your proof. Is this correct? $\endgroup$ – Lieuwe Vinkhuijzen Jun 21 '16 at 11:17
  • $\begingroup$ Sure. A nice extension indeed. $\endgroup$ – Shaull Jun 21 '16 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.