<p>Inspired by <a href="https://cstheory.stackexchange.com/questions/20883/techniques-for-showing-that-problem-is-in-hardness-limbo">Suresh's post</a>, 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.</p>

<blockquote>
  <p>What techniques and methods do exist to show that a $coNP$ problem might not have good characterization?</p>
</blockquote>

CC BY-SA 3.0
2015-10-15T17:49:16.063Z
@RickyDemer Edited the post according to your comment.
Mohammad Al-Turkistany
<cc.complexity-theory><proof-complexity>
Techniques for showing intermediate status between $\mathsf{NP \cap coNP}$ and coNP-completeness
Mohammad Al-Turkistany
# Techniques for showing intermediate status between $\mathsf{NP \cap coNP}$ and coNP-completeness

(Asked by: username_0 on 2015-10-15)

Inspired by [Suresh's post](https://cstheory.stackexchange.com/questions/20883/techniques-for-showing-that-problem-is-in-hardness-limbo), 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?

**Tags:** cc.complexity-theory, proof-complexity
> **Comments:**
> **username_0**: @RickyDemer Edited the post according to your comment.  

---

## 0 answers

