3
$\begingroup$

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.

$\endgroup$
1
  • 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$ Commented Nov 22, 2019 at 2:26

1 Answer 1

4
$\begingroup$

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

$\endgroup$
6
  • $\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
    Commented Nov 23, 2019 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$ Commented Nov 23, 2019 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
    Commented Nov 23, 2019 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
    Commented Nov 23, 2019 at 23:37
  • $\begingroup$ @NealYoung yes, in fact it works with recursive in place of r.e. $\endgroup$ Commented Nov 23, 2019 at 23:40

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.