0
$\begingroup$

$P$ means polynomial complexity. $S_p$ is class of all $P$_random sets, and $S_{pc}$ is class of all $P$ incomputable sets, is $S_{pc} \setminus S_p$ empty? If not empty, any example?

what is the result, if we replace $P$ complexity with $NP$?

Moreover, $S$ is class of all random sets, and $S_c$ is class of all incomputable sets, $S_{c}\setminus S $ is not empty, what is a set in the class $S_{c}\setminus S $,an immune set, productive set, or set of any other kind.

Improve this question
$\endgroup$
3
  • $\begingroup$ I do not know what these classes are. But you could note that $S_{pc} \setminus S_p = \varnothing$ is equivalent to $S_{pc} \subseteq S_p$; that is: every $P$ incomputable set is $P$_random. $\endgroup$ Commented Dec 20, 2019 at 2:23
  • $\begingroup$ Isn't this a duplicate of your previous question? mathoverflow.net/q/348681/1946. My answer there yesterday is the same as Dan's answer here. $\endgroup$ Commented Dec 20, 2019 at 9:31
  • $\begingroup$ @JoelDavidHamkins you answer my question, and I tried to rephrase the question and ask them separately, but found you have answered both of them, so I have to merge them, and have forgotten to delete this one which is answered by Dan. I have to keep this one not to let Dan's answer to be deleted with my post. $\endgroup$ Commented Dec 20, 2019 at 9:41

1 Answer 1

Reset to default
3
$\begingroup$

No, the differences are not empty. As an example, take any noncomputable sequence such that every bit is repeated. That is, the $(2n)$th bit is the same as the $(2n+1)$th bit, for all $n$. This will fail to be $P$-random.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.