[Solved]: Show that this language is in NP $\cap$ coNP

Problem Detail: 

Say $\ell: \{0,1\}^\ast \to \{0,1\}^\ast$ is a one-to-one polynomial-time computable function that preserves length. Consider the language $$L = \Bigl\{v \;\Big|\; \exists u: \bigl(u_1 = 1 ~~\text{and}~~ \ell(u) = v\bigr) \Bigr\}.$$ How do I prove that $L$ is in $\mathsf{NP} \cap \mathsf{coNP}$? Basically, what would appropriate witnesses for $L$ in $\mathsf{NP}$ and $\mathsf{coNP}$ be?

Asked By : wemblem

Answered By : Yuval Filmus

Hint: Use the fact that $\ell$ is one-to-one, and so to every $v$ there corresponds a unique $u$ such that $\ell(u) = v$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11696

3.2K people like this

 Download Related Notes/Documents