patternMinor
What does it mean when $A$ is a NP-Complete Problem but $\bar{A} = NP$?
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!
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.
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.