I am reading a paper where the authors prove that a certain problem is $\Sigma^1_1$-complete; in particular, it is also $\Sigma^1_1$-hard. Does this imply that the problem is not co-recursively enumerable (i.e., that its complement is not recursively enumerable)?
Asked
Active
Viewed 67 times
1 Answers
3
Yes, by a wide wide wide wide margin. $\Sigma^1_1$ is a truly gigantic class; it outstrips the entire arithmetical hierarchy (of which r.e./co-r.e. constitute merely the first nontrivial level), and even goes past its transfinite extension.
Note, however, that the superscript is crucial here: while $\Sigma^1_1$ is gigantic, $\Sigma^0_1$ is synonymous with r.e. So you should make sure that the authors are talking about $\Sigma^1_1$, rather than $\Sigma^0_1$, completeness.
Noah Schweber
- 245,398