-1

Can a NP-complete language be P-immune?

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

Bjørn Kjos-Hanssen
  • 4,485
  • 2
  • 25
  • 40
XL _At_Here_There
  • 1,070
  • 7
  • 17
  • The question whether a coNP-complete language can be P-immune is discussed at https://cstheory.stackexchange.com/questions/33312/poly-time-superset-of-np-complete-language-with-infinitely-many-strings-excluded/33316#33316 – Bjørn Kjos-Hanssen Oct 15 '17 at 17:27
  • 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? – Emil Jeřábek Oct 15 '17 at 18:42

1 Answers1

2

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.

Bjørn Kjos-Hanssen
  • 4,485
  • 2
  • 25
  • 40