HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problembarwhatbutmeancompletedoeswhen

Problem

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!

Solution

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.

Context

StackExchange Computer Science Q#35305, answer score: 7

Revisions (0)

No revisions yet.