World's most popular travel blog for travel bloggers.

[Answers] Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?

, , No Comments
Problem Detail: 

Assuming $\Sigma = \{ 0, 1\}$..

Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$?

So it is the same as showing that $\overline{L}\in NP$, but I'm not really sure on how to prove this.

Does anyone have an idea?

Asked By : TheEmeritus

Answered By : Yuval Filmus

Hint: Suppose we are given a word $w$ of length $n$ which is not in $L$, and let $w_1,\ldots,w_n$ be the words of length $n$ which are in $L$. A witness that $w \notin L$ is the list $w_1,\ldots,w_n$ (all different from $w$!) together with witnesses that $w_1,\ldots,w_n \in L$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback