Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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}$.

share|improve this answer
    
You have to show that NP is closed under concatenation too. –  frafl Mar 27 '13 at 18:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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