Skip to main content
Post Closed as "Duplicate" by Joel David Hamkins, CommunityBot
make the title informative
Link
Emil Jeřábek
  • 50.6k
  • 4
  • 162
  • 224

Is the difference class empty Are all $P$-noncomputable sets $P$-random?

Source Link

Is the difference class empty?

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