Can a NP-complete language be P-immune?
Why can't existence of P-immune languages separate NP from P?
$\begingroup$
$\endgroup$
-
$\begingroup$ The question whether a coNP-complete language can be P-immune is discussed at cstheory.stackexchange.com/questions/33312/… $\endgroup$ – Bjørn Kjos-Hanssen♦ Oct 15 '17 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$ – Emil Jeřábek supports Monica Oct 15 '17 at 18:42
$\begingroup$
$\endgroup$
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.
answered Oct 15 '17 at 17:30
