# Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?

A set is $\mathsf{P}$-immune iff it has no non-trivial $\mathsf{P}$ subset.

Is every $\mathsf{coNP}$-complete language $\mathsf{P}$-isomorphic to an $\mathsf{P}$-immune $\mathsf{coNP}$-complete language?

Joshua Grochow's answer to my previous questions shows the answer is negative assuming cryptographic conjectures. Is it possible to show the answer is negative only assuming $\mathsf{P}\neq\mathsf{NP}$?

As @Kaveh points out based upon a P isomorphism assumption (Bertman-Hartmanis conjecture) one only has to show the existence of one such language.

## migrated from mathoverflow.netDec 24 '15 at 12:37

This question came from our site for professional mathematicians.

• Migrated on request of OP. – Todd Trimble Dec 24 '15 at 12:36
• An earlier question by me on similar lines is here cstheory.stackexchange.com/q/33312/17763 – ARi Dec 24 '15 at 13:14
• Doesn't Josh's answer already answer this one as well? The complement of no NP-complete language is P-immune (assuming ...). – Kaveh Dec 24 '15 at 17:22
• I edited the question a bit to make it easier to read. By the way, you cannot get a positive answer without disproving one of the conjectures. I think it would have been better just to update your previous question asking if it is possible to show the same thing with weaker assumptions in place of posting a new question. Also note that by Berman-Hartmanis conjecture all coNP-complete languages are P-isomorphic. – Kaveh Dec 24 '15 at 17:58