<p>Assuming that</p>

<ul>
<li>pseudorandom generators and secure one‐way permutations exist,</li>
</ul>

<p>it follows that</p>

<ul>
<li>$\mathsf{NP}$‐complete sets are not $\mathsf P$‐immune.</li>
</ul>

<p>Christian Glaßer, A. Pavan, Alan L. Selman, and Samik Sengupta,
<a href="http://epubs.siam.org/doi/abs/10.1137/S009753970444421X" rel="nofollow noreferrer">Properties of NP‐Complete Sets</a>
SIAM J. Comput., 36(2), 516–542, 2006.</p>

CC BY-SA 3.0
2017-10-15T17:30:55.977Z
2017-10-15T17:41:08.927Z
2017-10-15T17:41:08.927Z
Bjørn Kjos-Hanssen
<p>Can a NP-complete language be P-immune?</p>

<p>Why can't existence of P-immune languages separate NP from P?</p>

CC BY-SA 3.0
2017-10-15T17:27:06.310Z
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
CC BY-SA 3.0
2017-10-15T18:42:18.230Z
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
<complexity-classes><fl.formal-languages><computability>
What is the relation between P-immune languages and NP-complete languages?
XL _At_Here_There
# What is the relation between P-immune languages and NP-complete languages?

(Asked by: username_0 on 2017-10-15)

Can a NP-complete language be P-immune?

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

**Tags:** complexity-classes, fl.formal-languages, computability

> **Comments:**
> **username_1**: 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  
> **username_2**: 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?  

---

## 1 answers

### Answer by username_1 on 2017-10-15. Score: 2 | Accepted answer

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](http://epubs.siam.org/doi/abs/10.1137/S009753970444421X)
SIAM J. Comput., 36(2), 516–542, 2006.


---

