Can a NP-complete language be P-immune?
Why can't existence of P-immune languages separate NP from P?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityCan a NP-complete language be P-immune?
Why can't existence of P-immune languages separate NP from P?
Assuming that
it follows that
Christian Glaßer, A. Pavan, Alan L. Selman, and Samik Sengupta, Properties of NP‐Complete Sets SIAM J. Comput., 36(2), 516–542, 2006.