Can a NP-complete language be P-immune?
Why can't existence of P-immune languages separate NP from P?
-1
$\begingroup$
$\endgroup$
closed as unclear what you're asking by user6973, Yuval Filmus, Kaveh, Emil Jeřábek, Mohammad Al-Turkistany Oct 15 '17 at 19:15
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
-
$\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 Oct 15 '17 at 18:42
2
$\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
