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 Sep 18 '15 at 7:23
  • $\begingroup$ See also cs.stackexchange.com/q/9556/755 $\endgroup$ – D.W. Sep 18 '15 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 Sep 18 '15 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 Sep 18 '15 at 17:54
  • $\begingroup$ If $R$ returns a truth value, that is it is a predicate, what is there to misunderstand? $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ Why is $w\#y$ a single string, but $wy$ wouldn't be? $\endgroup$ – mavavilj Sep 18 '15 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 Sep 18 '15 at 8:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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