2

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?

Community
  • 1
Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • As far as I'm aware, graph isomorphism is not even known to be in coQMASUBEXP, so it would presumably be difficult to show that there is a GI-complete problem in coNP. $;$ –  Oct 15 '15 at 17:43
  • @RickyDemer Edited the post according to your comment. – Mohammad Al-Turkistany 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}$ –  Oct 15 '15 at 17:52

0 Answers0