# Techniques for showing intermediate status between $\mathsf{NP \cap coNP}$ and coNP-completeness

Inspired by Suresh's post, for a new problem in $\mathsf{coNP}$, whose true proof complexity is intermediate between $\mathsf{NP \cap coNP}$ and being coNP-complete, I am interested in methods which show that it is probably hard to prove the existence of good characterization.

What techniques and methods do exist to show that a $coNP$ problem might not have good characterization?

• As far as I'm aware, graph isomorphism is not even known to be in coQMA<sub>SUBEXP</sub>, so it would presumably be difficult to show that there is a GI-complete problem in coNP. $\;$
– user6973
Oct 15 '15 at 17:43
• @RickyDemer Edited the post according to your comment. Oct 15 '15 at 17:49
• On the other hand, one "such method is to show that the problem is" coGI-complete. $\hspace{1.35 in}$
– user6973
Oct 15 '15 at 17:52