# Is there a well-defined notion of an “R/poly” complexity class?

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?

• 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. Commented Sep 7, 2023 at 15:20

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

• 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)$ Commented Sep 10, 2023 at 20:22
• 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. Commented Sep 12, 2023 at 9:32
• 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$. Commented Sep 12, 2023 at 19:12
• 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. Commented Sep 12, 2023 at 20:02
• 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). Commented Sep 13, 2023 at 4:15