At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and co-RE. However, something else defined through computability theory is the concept of an immune set. Immune sets are ones where you are unable to enumerate even an infinite subset.

My question is this: is there a complexity class of decision problems where an infinite subset of "yes" instances can be enumerated, and is there a "better" name for it than "not immune"? I ask this because complexity classes are typically named for what they are, but "immune" describes what the decision problem is not.

  • 3
    $\begingroup$ I doubt it. "Not immune" is precisely the concept you're going for - I don't know of any theorem saying that "not immune" is equivalent to "yes [something]". I'm not sure I'd call "not immune" a complexity class though - it's more like the complement of one. If a set is immune then any set which reduces to it with infinite image must also be immune. So immunity is almost downward closed under reductions (a property we generally like complexity classes to have). Calling this a complexity class would be like calling "not in NP" a complexity class. Just feels strange. $\endgroup$ – Joshua Grochow Nov 22 '19 at 2:26

If a set $A$ is Turing reducible to a set $B$ then we say that $B$ computes $A$.

Every noncomputable set $A$ computes an immune set, namely $\hat A = \{\sigma: \sigma \text{ is a prefix of }A\}$.

(If $A$ is a set of strings then we first turn it onto a [i.e. replace it by a Turing equivalent] set of integers or equivalently an infinite binary sequence before applying the hat operation.)

For instance if $A$ is the set of prime numbers then we may write $$A=A(0)A(1)A(2)\dots=00110101000101000101\dots$$ and then $\sigma=0011010$ is a prefix of $A$ whereas $010011$ is not.

Therefore the complexity class of sets that compute only non-immune sets is just the computable sets $\mathsf{R}$.

| cite | improve this answer | |
  • $\begingroup$ (i) What do you mean by "a set computes another set" (used twice above)? (ii) What does it mean for a string $\sigma$ to be a prefix of a set $A$? Do you mean, we concatenate all of the strings in $A$, to get an infinite string, and then let $\sigma$ be any prefix of that string? (But with this interpretation your construction doesn't have to give an immune set. Let $A$ contain the unary encodings of TMs that halt on blank tape. Then $A$ is not computable, but $\hat A = 1^*$, which is surely not immune.) $\endgroup$ – Neal Young Nov 23 '19 at 18:33
  • 1
    $\begingroup$ @NealYoung if $A$ is a set of strings then we first turn it onto a set of integers or equivalently an infinite binary sequence before applying the hat operation. $\endgroup$ – Bjørn Kjos-Hanssen Nov 23 '19 at 19:36
  • $\begingroup$ I don't understand your correction. For example, I can encode the halting problem by a set $$A = \{f(M) : M \text{ halts on blank tape}\}$$ where $f(M)$ is computed as follows: encode $M$ in binary by a standard encoding, let $i(M)$ be the integer representing $M$ in that encoding, then take $f(M) = 2^{i(M)}-1$. Then $A$ is an undecidable set of integers (encoded in binary), but all its integers, in binary, contain only 1's, so again $\hat A = 1^*$. What am I missing? $\endgroup$ – Neal Young Nov 23 '19 at 23:02
  • $\begingroup$ I see, you are assuming that the strings in $A$ are encoded in something like a set of prefix-free codewords, so from each prefix $\sigma$ I can uniquely determine the corresponding strings in $A$. Given this, if $\hat A$ is not immune, I can recursively enumerate arbitrarily long strings in $\hat A$, so can recursively enumerate $A$. So if $A$ is not r.e., then $\hat A$ is not immune. $\endgroup$ – Neal Young Nov 23 '19 at 23:37
  • $\begingroup$ @NealYoung yes, in fact it works with recursive in place of r.e. $\endgroup$ – Bjørn Kjos-Hanssen Nov 23 '19 at 23:40

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.