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.