<p>There is nothing stopping you from defining the class, though I don’t recall seeing it studied.</p>
<p>Actually, I can see two reasonable definitions for this class. The first one, which follows more literally the notation, is that <span class="math-container">$L\in\mathrm{R/poly}$</span> iff there is a recursive predicate <span class="math-container">$P(x,y)$</span> and an advice function <span class="math-container">$a\colon\mathbb N\to\{0,1\}^*$</span> such that <span class="math-container">$|a(n)|\le n^{O(1)}$</span> and <span class="math-container">$x\in L\iff P(x,a(|x|))$</span>. I can’t say anything about this class (I don’t even know if it includes RE).</p>
<p>The second possibility is that <span class="math-container">$L\in\mathrm{R/poly}$</span> iff there is a TM <span class="math-container">$M(x,y)$</span> and an advice function <span class="math-container">$a\colon\mathbb N\to\{0,1\}^*$</span> such that <span class="math-container">$|a(n)|\le n^{O(1)}$</span>, and for each <span class="math-container">$x$</span>, <span class="math-container">$M(x,a(|x|))$</span> halts and decides whether <span class="math-container">$x\in L$</span>. (However, <span class="math-container">$M(x,y)$</span> may not necessarily halt for other choices of <span class="math-container">$y$</span>.) Strictly speaking, this should be called <span class="math-container">$\mathrm{RE/poly\cap coRE/poly}$</span>, I guess; but anyway, this class seems to be more robust, and I can say something about it.</p>
<p>Under the second definition, R/poly includes RE; moreover, it includes all languages computable with polynomially many RE oracle queries, and languages computable with exponentially many parallel RE oracle queries.</p>
<p>To see this, let <span class="math-container">$L\in\mathrm{RE}$</span>, and let <span class="math-container">$M$</span> be a Turing machine that accepts <span class="math-container">$L$</span>. We define the advice to be <span class="math-container">$a(n)=\#L_n$</span> (written in binary so that it has <span class="math-container">$O(n)$</span> bits), where <span class="math-container">$L_n=L\cap\Sigma^n$</span>. Given an input <span class="math-container">$x$</span> of length <span class="math-container">$n$</span>, and knowing <span class="math-container">$a(n)$</span>, we can compute <span class="math-container">$L_n$</span> (and then check whether <span class="math-container">$x\in L_n$</span>) by running in parallel (using dovetailing) <span class="math-container">$M$</span> on all inputs <span class="math-container">$w$</span> of length <span class="math-container">$n$</span>, until <span class="math-container">$a(n)$</span> many of the instances halt and accept; then we know that the remaining instances cannot accept, and we can stop the search.</p>
<p>If <span class="math-container">$L$</span> is itself not in RE, but it is computable with an RE oracle <span class="math-container">$L'$</span> to which it only makes queries of length bounded by a polynomial <span class="math-container">$p(n)$</span>, let the advice be <span class="math-container">$\sum_{m\le p(n)}\#L'_m$</span>, using a similar argument. More generally, this shows that R/poly is closed under polynomially bounded Turing reductions.</p>
<p>If <span class="math-container">$L$</span> is computable by a TM <span class="math-container">$M$</span> with polynomially many queries to an RE oracle, which we may assume w.l.o.g. to be the halting problem <span class="math-container">$H$</span>, then <span class="math-container">$L$</span> is also computable with polynomially bounded queries to <span class="math-container">$H$</span>, hence it is in R/poly by the previous paragraph: we successively determine answers to the oracle queries by asking <span class="math-container">$H$</span> polynomially many questions of the form “what is the answer to the <span class="math-container">$i$</span>th oracle query made by <span class="math-container">$M$</span> on input <span class="math-container">$x$</span>, assuming the previous oracle queries were answered by <span class="math-container">$a_0,\dots,a_{i-1}\in\{0,1\}$</span>” (this can be expressed as a polynomially long query to <span class="math-container">$H$</span>). A similar argument applies if <span class="math-container">$L$</span> is computable with exponentially many parallel (= non-adaptive) oracle queries to <span class="math-container">$H$</span>.</p>
<p>To place an upper bound on R/poly, for any <span class="math-container">$L\in\mathrm{R/poly}$</span>, the Kolmogorov complexity of <span class="math-container">$L_n$</span> (as a <span class="math-container">$2^n$</span>-bit string) is <span class="math-container">$n^{O(1)}$</span>: to compute <span class="math-container">$L_n$</span>, we only need to specify <span class="math-container">$n$</span>, <span class="math-container">$a(n)$</span>, and a (constant-size) description of the TM <span class="math-container">$M$</span> from the definition. In contrast, a random string has Kolmogorov complexity about <span class="math-container">$2^n$</span>. Thus, most languages are not in R/poly, or even in R/subexp.</p>
<p>This also shows that R/poly does not contain <span class="math-container">$\Delta_2$</span>, or even <span class="math-container">$\mathrm{EXP}^H$</span>, as we can compute in this class the lexicographically first string of length <span class="math-container">$2^n$</span> and Kolmogorov complexity <span class="math-container">$\ge2^n$</span> by binary search (using queries expressing the RE predicate “every <span class="math-container">$2^n$</span>-bit string extending <span class="math-container">$a_0\dots a_{i-1}$</span> is computed by some program of length <span class="math-container">$&lt;2^n$</span>”).</p>
<p>Furthermore, a generalization of the Kolmogorov complexity argument shows that there is a strict hierarchy: if <span class="math-container">$\alpha,\beta\colon\mathbb N\to\mathbb N$</span> are functions such that <span class="math-container">$\alpha(n)\le\beta(n)\le2^n$</span> and <span class="math-container">$\beta(n)-\alpha(n)\ge2\log n$</span> or so, then <span class="math-container">$\mathrm R/\alpha(n)\subsetneq\mathrm R/\beta(n)$</span>, as all languages <span class="math-container">$L\in\mathrm R/\alpha(n)$</span> have Kolmogorov complexity <span class="math-container">$K(L_n)\le\alpha(n)+O(\log n)$</span>, whereas <span class="math-container">$\mathrm R/\beta(n)$</span> contains a language <span class="math-container">$L$</span> with <span class="math-container">$K(L_n)\ge\beta(n)$</span>.</p>
<p>Come to think of it, Kolmogorov complexity provides an exact characterization of R/poly:
<span class="math-container">$$L\in\mathrm{R/poly}\iff\exists\text{ a polynomial $p$ }\forall n\in\mathbb N\:K(L_n)\le p(n).$$</span>
We have already seen the left-to-right implication; for the converse, we can use as advice <span class="math-container">$a(n)$</span> a description of an algorithm that computes <span class="math-container">$L_n$</span>.</p>

CC BY-SA 4.0
2023-09-10T20:22:44.610Z
How large is R/poly? Does it contain $Δ^0_2$, and does it equal ALL?(I presume not.) But how far does R/poly extend? This also raises the question of if $Δ^0_n/poly$ contains $Δ^0_(n+1)$
Colonizor48
CC BY-SA 4.0
2023-09-12T09:32:33.153Z
R/poly does not contain $\Delta_2$, and does not equal ALL; I included this extra information in the answer. I also realized that the description of R/poly is ambiguous, hence I explicitly pointed out the definition which I am operating with.
Emil Jeřábek
CC BY-SA 4.0
2023-09-12T19:12:16.940Z
For the first version of R/poly, R/poly = ∪{f/poly: computable f}, which by diagonalization does not include RE.  For the second version of R/poly, another characterization is R/poly = (P/poly)$^H$.
Dmytro Taranovsky
CC BY-SA 4.0
2023-09-12T20:02:37.913Z
Does R/subexp contain $EXP^H$? where instead of merely polynomial advice we allow sub-exponential advice. Though R/EXP and indeed for any class C C/EXP trivially equals ALL.
Colonizor48
CC BY-SA 4.0
2023-09-13T04:15:57.847Z
All languages in R/subexp have subexponential Kolmogorov complexity, whereas $\mathrm{EXP}^H$ contains languages with exponential Kolmogorov complexity, thus the former cannot include the latter. (Btw: EXP/exp or even PSPACE/exp equals ALL, but e.g. P/exp does not, as a polytime-machine can only access polynomially many bits of the advice).
Emil Jeřábek
CC BY-SA 4.0
2023-09-07T07:26:52.070Z
2023-09-12T11:44:02.753Z
2023-09-12T11:44:02.753Z
Emil Jeřábek
<p>This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without this advice string. I think you might be able to just iterate through all possible advice strings, but it could be undecidable if a given advice string is the correct one, as a TM could act unpredictably and undecidably with the wrong one. Also, I presume that if R/poly is well defined and distinct, we could also define an “R/subexp” class. And, more broadly, the space complexity of the advice string could perhaps be a good measure of “how undecidable” an undecidable problem is. If R/poly is well defined and distinct, what is known about it if anything? Does it contain RE?</p>

CC BY-SA 4.0
2023-09-07T15:20:44.533Z
Note that R/poly, like P/poly, contains a unary representative from every Turing degree. (For P/poly, this is maybe less interesting, b/c the relevant notion of reduction there is FP or FP/poly, but for R/poly, it seems more interesting.) It is interesting that R/poly seems to really separate out the question of the power of advice from the question of the power of circuits.
Joshua Grochow
<complexity-classes><computability><decidability><advice-and-nonuniformity>
Is there a well-defined notion of an “R/poly” complexity class?
Colonizor48
# Is there a well-defined notion of an “R/poly” complexity class?

(Asked by: username_0 on 2023-09-07)

This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without this advice string. I think you might be able to just iterate through all possible advice strings, but it could be undecidable if a given advice string is the correct one, as a TM could act unpredictably and undecidably with the wrong one. Also, I presume that if R/poly is well defined and distinct, we could also define an “R/subexp” class. And, more broadly, the space complexity of the advice string could perhaps be a good measure of “how undecidable” an undecidable problem is. If R/poly is well defined and distinct, what is known about it if anything? Does it contain RE?

**Tags:** complexity-classes, computability, decidability, advice-and-nonuniformity

> **Comments:**
> **username_1**: Note that R/poly, like P/poly, contains a unary representative from every Turing degree. (For P/poly, this is maybe less interesting, b/c the relevant notion of reduction there is FP or FP/poly, but for R/poly, it seems more interesting.) It is interesting that R/poly seems to really separate out the question of the power of advice from the question of the power of circuits.  

---

## 1 answers

### Answer by username_2 on 2023-09-07. Score: 8 | Accepted answer

There is nothing stopping you from defining the class, though I don’t recall seeing it studied.

Actually, I can see two reasonable definitions for this class. The first one, which follows more literally the notation, is that $L\in\mathrm{R/poly}$ iff there is a recursive predicate $P(x,y)$ and an advice function $a\colon\mathbb N\to\{0,1\}^\*$ such that $|a(n)|\le n^{O(1)}$ and $x\in L\iff P(x,a(|x|))$. I can’t say anything about this class (I don’t even know if it includes RE).

The second possibility is that $L\in\mathrm{R/poly}$ iff there is a TM $M(x,y)$ and an advice function $a\colon\mathbb N\to\{0,1\}^\*$ such that $|a(n)|\le n^{O(1)}$, and for each $x$, $M(x,a(|x|))$ halts and decides whether $x\in L$. (However, $M(x,y)$ may not necessarily halt for other choices of $y$.) Strictly speaking, this should be called $\mathrm{RE/poly\cap coRE/poly}$, I guess; but anyway, this class seems to be more robust, and I can say something about it.

Under the second definition, R/poly includes RE; moreover, it includes all languages computable with polynomially many RE oracle queries, and languages computable with exponentially many parallel RE oracle queries.

To see this, let $L\in\mathrm{RE}$, and let $M$ be a Turing machine that accepts $L$. We define the advice to be $a(n)=\#L\_n$ (written in binary so that it has $O(n)$ bits), where $L\_n=L\cap\Sigma^n$. Given an input $x$ of length $n$, and knowing $a(n)$, we can compute $L\_n$ (and then check whether $x\in L\_n$) by running in parallel (using dovetailing) $M$ on all inputs $w$ of length $n$, until $a(n)$ many of the instances halt and accept; then we know that the remaining instances cannot accept, and we can stop the search.

If $L$ is itself not in RE, but it is computable with an RE oracle $L'$ to which it only makes queries of length bounded by a polynomial $p(n)$, let the advice be $\sum\_{m\le p(n)}\#L'\_m$, using a similar argument. More generally, this shows that R/poly is closed under polynomially bounded Turing reductions.

If $L$ is computable by a TM $M$ with polynomially many queries to an RE oracle, which we may assume w.l.o.g. to be the halting problem $H$, then $L$ is also computable with polynomially bounded queries to $H$, hence it is in R/poly by the previous paragraph: we successively determine answers to the oracle queries by asking $H$ polynomially many questions of the form “what is the answer to the $i$th oracle query made by $M$ on input $x$, assuming the previous oracle queries were answered by $a\_0,\dots,a\_{i-1}\in\{0,1\}$” (this can be expressed as a polynomially long query to $H$). A similar argument applies if $L$ is computable with exponentially many parallel (= non-adaptive) oracle queries to $H$.

To place an upper bound on R/poly, for any $L\in\mathrm{R/poly}$, the Kolmogorov complexity of $L\_n$ (as a $2^n$-bit string) is $n^{O(1)}$: to compute $L\_n$, we only need to specify $n$, $a(n)$, and a (constant-size) description of the TM $M$ from the definition. In contrast, a random string has Kolmogorov complexity about $2^n$. Thus, most languages are not in R/poly, or even in R/subexp.

This also shows that R/poly does not contain $\Delta\_2$, or even $\mathrm{EXP}^H$, as we can compute in this class the lexicographically first string of length $2^n$ and Kolmogorov complexity $\ge2^n$ by binary search (using queries expressing the RE predicate “every $2^n$-bit string extending $a\_0\dots a\_{i-1}$ is computed by some program of length $<2^n$”).

Furthermore, a generalization of the Kolmogorov complexity argument shows that there is a strict hierarchy: if $\alpha,\beta\colon\mathbb N\to\mathbb N$ are functions such that $\alpha(n)\le\beta(n)\le2^n$ and $\beta(n)-\alpha(n)\ge2\log n$ or so, then $\mathrm R/\alpha(n)\subsetneq\mathrm R/\beta(n)$, as all languages $L\in\mathrm R/\alpha(n)$ have Kolmogorov complexity $K(L\_n)\le\alpha(n)+O(\log n)$, whereas $\mathrm R/\beta(n)$ contains a language $L$ with $K(L\_n)\ge\beta(n)$.

Come to think of it, Kolmogorov complexity provides an exact characterization of R/poly:
$$L\in\mathrm{R/poly}\iff\exists\text{ a polynomial $p$ }\forall n\in\mathbb N\:K(L\_n)\le p(n).$$
We have already seen the left-to-right implication; for the converse, we can use as advice $a(n)$ a description of an algorithm that computes $L\_n$.

> **Comments:**
> **username_0**: How large is R/poly? Does it contain $Δ^0_2$, and does it equal ALL?(I presume not.) But how far does R/poly extend? This also raises the question of if $Δ^0_n/poly$ contains $Δ^0_(n+1)$  
> **username_2**: R/poly does not contain $\Delta_2$, and does not equal ALL; I included this extra information in the answer. I also realized that the description of R/poly is ambiguous, hence I explicitly pointed out the definition which I am operating with.  
> **username_3**: For the first version of R/poly, R/poly = ∪{f/poly: computable f}, which by diagonalization does not include RE.  For the second version of R/poly, another characterization is R/poly = (P/poly)$^H$.  
> **username_0**: Does R/subexp contain $EXP^H$? where instead of merely polynomial advice we allow sub-exponential advice. Though R/EXP and indeed for any class C C/EXP trivially equals ALL.  
> **username_2**: All languages in R/subexp have subexponential Kolmogorov complexity, whereas $\mathrm{EXP}^H$ contains languages with exponential Kolmogorov complexity, thus the former cannot include the latter. (Btw: EXP/exp or even PSPACE/exp equals ALL, but e.g. P/exp does not, as a polytime-machine can only access polynomially many bits of the advice).  

---

