7

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}$?

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.

Community
  • 1
ARi
  • 405
  • 2
  • 8
  • Migrated on request of OP. –  Dec 24 '15 at 12:36
  • 1
    An earlier question by me on similar lines is here http://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
  • 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 all coNP-complete languages are P-isomorphic. – Kaveh Dec 24 '15 at 17:58

1 Answers1

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).

Kaveh
  • 21,577
  • 8
  • 82
  • 183