patternMinor
P is contained in NP ∩ Co-NP?
Viewed 0 times
containedstackoverflowprogramming
Problem
How should I show that ${\sf P}$ is contained in ${\sf NP} \cap {\sf CoNP}$?
I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.
I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.
Solution
A language $L$ is in $P$, we have an algorithm $A$ that runs in polynomial time that recognizes it.
It is easy to show that the complement of $L$, $\bar{L}$, is in $P$. The algorithm to recognize it is to simulate $A$ but just invert the answer.
As long as $\bar{L}$ is in P (thus in NP), $L$ is in $co-NP$.
It is easy to show that the complement of $L$, $\bar{L}$, is in $P$. The algorithm to recognize it is to simulate $A$ but just invert the answer.
As long as $\bar{L}$ is in P (thus in NP), $L$ is in $co-NP$.
Context
StackExchange Computer Science Q#11725, answer score: 7
Revisions (0)
No revisions yet.