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

  • $\begingroup$ @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"? $\endgroup$
    – mavavilj
    Commented Sep 18, 2015 at 7:23
  • $\begingroup$ See also cs.stackexchange.com/q/9556/755 $\endgroup$
    – D.W.
    Commented Sep 18, 2015 at 8:57
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Sep 18, 2015 at 17:50
  • $\begingroup$ @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\}$ $\endgroup$
    – mavavilj
    Commented Sep 18, 2015 at 17:54
  • $\begingroup$ If $R$ returns a truth value, that is it is a predicate, what is there to misunderstand? $\endgroup$
    – Raphael
    Commented Sep 18, 2015 at 17:56

1 Answer 1


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

  • $\begingroup$ Why is $w\#y$ a single string, but $wy$ wouldn't be? $\endgroup$
    – mavavilj
    Commented Sep 18, 2015 at 7:59
  • 2
    $\begingroup$ @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$. $\endgroup$
    – Kittsil
    Commented Sep 18, 2015 at 8:04

Your Answer

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

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