-1
$\begingroup$

Can a NP-complete language be P-immune?

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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