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.