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

Question

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?

Answer 1

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