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?

  • $\begingroup$ 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. $\;$ $\endgroup$
    – user6973
    Oct 15, 2015 at 17:43
  • $\begingroup$ @RickyDemer Edited the post according to your comment. $\endgroup$ Oct 15, 2015 at 17:49
  • $\begingroup$ On the other hand, one "such method is to show that the problem is" coGI-complete. $\hspace{1.35 in}$ $\endgroup$
    – user6973
    Oct 15, 2015 at 17:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.