# What does it mean when $A$ is a NP-Complete Problem but $\bar{A} = NP$?

I'm still in the process of grokking computational complexity.

However, I came across a statement like the above in an old midterm paper I'm reviewing, and I'm not sure I completely follow its logic.

$NP$ is the class of solveable decision problems that can be verified in polynomial time.

So when we say that $A$ is a NP Complete problem, it is understandably contained within the $NP$ class.

However, if $\bar{A}$ is included in the class $NP$, wouldn't these two postulates essentially indicate that ALL problems are $NP$?

Any insight into how to look at this would be much appreciated!

• Hi Andw, this can mean that $A$ is co-NP as well, just draw the Venn diagram – Olórin Dec 15 '14 at 5:48

## 1 Answer

If $A$ is ${\sf NP}$-complete and $\bar A$ is in $\sf NP$ then we can show that ${\sf NP = coNP}$. This would imply that the polynomial hierarchy collapses to the first level, which implies ${\sf NP = coNP = PH}$.

However, this implies not that all problems are in NP. Just an easy example. There are problems like the halting that are undecidable, and they will remain undecidable even if ${\sf NP = coNP}$, since the proof that the halting problem is undecidable does not use the concept of $\sf NP$ at all.