I have the following question on an assignment, and despite asking my prof, I can't get a grasp on it..

Let $L_1, L_2$ be languages in ${\sf NP}$. Using the definition of ${\sf NP}$ via relations and quantifiers (not the non-deterministic Turing machines) prove that the following language is in ${\sf NP}$: $L=\{ x | x \in L_1 \text{ or } xx \in L_2 \}$, where $xx$ is two concatenated copies of $x$.

Her notes say the following on this:

Let $L\subseteq\Sigma^{*}$. We say $L\in{\sf NP}$ if there is a two-place predicate $R\subseteq\Sigma^{*}\times\Sigma^{*}$ such that $R$ is computable in polynomial time, and such that for some $c,d\in\mathbb{N}$ we have $\forall x\in\Sigma^{*},x\in L\iff\exists y\in\Sigma^{*},|y|\leq c|x|^d$ and $R(x,y)$.

I would imagine that this is a well known definition (though possibly worded differently)... but I don't know where else I can get details on it. My textbook has a somewhat similar definition, but it doesn't talk about this $c,d\in\mathbb{N}$ stuff..

A verifier for a language $A$ is an algorithm $V$, where $$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$ We measure the time of a verifier only in terms of the length of $w$, so a polynomial time verifier runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier.

The $y$ in the first definition is supposed to be analogous to $c$ in the second; it is a certificate or witness used by the verifier. But that's all I can understand between the two.

Now... what I think I know about this question is that $R(x,y)$ is supposed to be a verifier for $L$, while $R_1(x,y_1)$ is a verifier for $L_1$ and $R_2(x,y_2)$ is a verifier for $L_2$. She said something about $y=\langle y_1, y_2\rangle$ being an encoding of the two certificates for the verifiers $R_1$ and $R_2$. But from there I'm lost. I have no idea how to answer this question even after asking for help two or three times.

Anybody here able to help? Thanks in advance.


1 Answer 1


I think I just realized, after finding a similar problem online, that this is asking to simply show that ${\sf NP}$ is closed under union. Can anybody give any insight into whether or not this is a proper solution, or if I'm missing anything? I mostly understand my answer, but I don't really know what I'm doing with the $c$ and $d$ constants... I put them in there because I feel like I'm going to need to.

This question is asking to prove that ${\sf NP}$ is closed under union. It is the same as asking if $L=L_{1}\cup L_{2}$ is in ${\sf NP}$.

Since $L_{1}$ and $L_{2}$ are both in ${\sf NP}$, it follows that they both have polynomial time verifiers $R_i(x_i,y_i)$ that evaluate to true when $y_{i}$ is a valid certificate/witness for $x_i\in L_i$, where $i\in \{1,2\}$.

To show that $L=L_1\cup L_2$ is also in ${\sf NP}$, we need to construct a polynomial-time verifier $R(x,y)$. The certificate $y=\langle y_1,y_2 \rangle$ for $L$ will be an encoding of the two certificates $y_1$ and $y_2$ in such a way that $R(x,y)$ evaluates to true when $\displaystyle\bigvee_{1\leq i\leq 2} R_i(x,y_i)$ evaluates to true.

Given that $R_{i}(x_i,y_i)$ for $i\in\{1,2\}$ are polynomial time verifiers with running time $O(c_i|x_i|^{d_i})$ for some $c,d\in\mathbb{N}$, $R(x,y)$ will have a running time of at most $O(2\cdot max(c_i)|x|^{max(d_i)})$, which is still polynomial. Therefore, $L\in {\sf NP}$.

  • $\begingroup$ You have to show that NP is closed under concatenation too. $\endgroup$
    – frafl
    Mar 27, 2013 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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