<p>Josh's answer uses two conjectures and 
both of them are considered to be highly likely to be correct by experts 
even if not proven yet.
A positive answer means that at least one of the two conjecture is incorrect.
That would be a major very surprising result.
In other words, 
it is highly unlikely that the answer to your question is positive, and
even if the answer is positive, 
it is not possible to prove it at this time 
(otherwise we would have already refuted one of those conjectures).</p>

CC BY-SA 3.0
2015-12-26T23:08:06.207Z
2015-12-26T23:08:06.207Z
Kaveh
<p>A set is <em>$\mathsf{P}$-immune</em> iff 
it has no non-trivial $\mathsf{P}$ subset.</p>

<blockquote>
  <p>Is every $\mathsf{coNP}$-complete language $\mathsf{P}$-isomorphic to
  an $\mathsf{P}$-immune $\mathsf{coNP}$-complete language?</p>
</blockquote>

<p><a href="https://cstheory.stackexchange.com/a/33316/">Joshua Grochow's answer</a> 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}$?</p>

<p>Or show the answer as positive with  additional assumptions.</p>

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

CC BY-SA 3.0
2015-12-24T13:14:30.720Z
An earlier question by me on similar lines is here http://cstheory.stackexchange.com/q/33312/17763
ARi
CC BY-SA 3.0
2015-12-24T17:22:55.157Z
Doesn't Josh's answer already answer this one as well? The complement of _no_ NP-complete language is P-immune (assuming ...).
Kaveh
CC BY-SA 3.0
2015-12-24T17:58:18.623Z
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](https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture) all coNP-complete languages are P-isomorphic.
Kaveh
<cc.complexity-theory><np-complete><structural-complexity>
Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?
ARi
# Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?

(Asked by: username_0 on 2015-12-22)

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](https://cstheory.stackexchange.com/a/33316/) 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}$?

Or show the answer as positive with additional assumptions.

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

**Tags:** cc.complexity-theory, np-complete, structural-complexity
> **Comments:**
> **username_0**: An earlier question by me on similar lines is here http://cstheory.stackexchange.com/q/33312/17763  
> **username_1**: Doesn't Josh's answer already answer this one as well? The complement of _no_ NP-complete language is P-immune (assuming ...).  
> **username_1**: 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](https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture) all coNP-complete languages are P-isomorphic.  

---

## 1 answers

### Answer by username_1 on 2015-12-26. Score: 4

Josh's answer uses two conjectures and
both of them are considered to be highly likely to be correct by experts
even if not proven yet.
A positive answer means that at least one of the two conjecture is incorrect.
That would be a major very surprising result.
In other words,
it is highly unlikely that the answer to your question is positive, and
even if the answer is positive,
it is not possible to prove it at this time
(otherwise we would have already refuted one of those conjectures).


---

