# Notation: $L_R = \{w\#y\space|\space R(w,y)\}$?

What is the set $$L_R = \{w\#y\space|\space R(w,y)\}$$

Specifically what kind of conditional is $R(w,y)$?
Also what's the purpose of $\#$?

This comes from page 2 of the Clay paper on P vs NP: http://www.claymath.org/sites/default/files/pvsnp.pdf

• @Kittsil This is from the Clay N=NP? paper: claymath.org/sites/default/files/pvsnp.pdf. Page 2. What I don't get is what kind of conditional is R(w,y)? I'm guessing the definition should be read "w#ys such that R(w,y) exists", but is the condition "R(w,y) exists"? – mavavilj Sep 18 '15 at 7:23
• This has nothing to do with NP per se, the notation is standard in formal languages. In mathematics, actually. It's just set builder notation. – Raphael Sep 18 '15 at 17:50
• @Raphael It's the $R(w,y)$ conditional that I didn't understand. I've never seen sets of the form $\{x \space | \space f(x)\}$, where the value of the conditional has been abstracted out, but rather e.g. $\{x \space | \space f(x)=1\}$ – mavavilj Sep 18 '15 at 17:54
• If $R$ returns a truth value, that is it is a predicate, what is there to misunderstand? – Raphael Sep 18 '15 at 17:56

This set is a formal way of expressing a "checking set." What this is asking is, "Is $y$ a valid output for $w$, where the space of all valid input/output pairs is the binary relation $R$?"
Let $\Sigma_i$ be the alphabet of the input and $\Sigma_o$ be the alphabet of outputs. The checking relation, $R\subseteq\Sigma_i^* \times \Sigma_o^*$ is the binary relation $R(w,y)$ that returns true if $y$ is a valid solution to $x$, and false otherwise.
(Note here that a relation can be expressed as a subset of the parameter spaces, $R\subseteq\Sigma_i^* \times \Sigma_o^*$, or as a function $R(w,y)$ that returns true or false. The functional form $R(w,y)$ can be viewed as the question, "Is $(w,y)\in R$?")
Finally, the symbol $\#$ in this definition is just a specific symbol not in $\Sigma_i$. Because a Turing machine only accepts a single string, you need some way of parameterizing your single input into two parameters, $w$ and $y$.
• Why is $w\#y$ a single string, but $wy$ wouldn't be? – mavavilj Sep 18 '15 at 7:59
• @mavavilj $wy$ is still a single string. But how do you know where $w$ end and $y$ begins? $010101$ could be $w=0101$ and $y=01$, or $w=010$ and $y=101$. Since $\#$ is not in the input alphabet, it is clear where $w$ ends and $y$ begins in $w\#y$. – Kittsil Sep 18 '15 at 8:04