7
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Sep 7, 2023 at 15:20

1 Answer 1

8
$\begingroup$

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

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

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.