-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$ The question whether a coNP-complete language can be P-immune is discussed at cstheory.stackexchange.com/questions/33312/… $\endgroup$ Oct 15, 2017 at 17:27
  • $\begingroup$ What on earth is the meaning of the first thing ending with a question mark? Is it possible to write it as an English sentence? $\endgroup$ Oct 15, 2017 at 18:42

1 Answer 1

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.