Can a NP-complete language be P-immune?

Why can't existence of P-immune languages separate NP from P?


Assuming that

  • pseudorandom generators and secure one‐way permutations exist,

it follows that

  • $\mathsf{NP}$‐complete sets are not $\mathsf P$‐immune.

Christian Glaßer, A. Pavan, Alan L. Selman, and Samik Sengupta, Properties of NP‐Complete Sets SIAM J. Comput., 36(2), 516–542, 2006.


Not the answer you're looking for? Browse other questions tagged or ask your own question.