P is contained in NP ∩ Co-NP?

Question

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.

Answer 1

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$.

Answer 2

P can be defined as a set of problems that can be decided by a deterministic Turing machine in polynomial time.

NP can be defined as a set of problems whose solutions can be accepted by a non-deterministic Turing machine in polynomial time. Similarly co-NP is a set of problems whose non-solutions can be accepted by a non-deterministic Turing machine in polynomial time.

Since every deterministic TM is also a non-deterministic one, if a problem is in $P$, you can use its decision TM to check solutions and non-solution in the definition of NP and co-NP.

Answer 3

There is already an answer addressing the NTM definition of $\mathbf{NP}$, so let me address the equivalent definition based on proof systems. (For a proof, check your favorite computational complexity textbook.)

$\mathbf{P}$ is the class of problems solvable by a TM in polynomial time (in the length of the input). $\mathbf{NP}$ is the class of problems such that for every such problem $P$ there is a TM called a verifier $V$. As input, $V$ receives, in addition to the standard input $x$, a witness $y$ whose length is bounded by a polynomial in $|x|$ (i.e., $|w| \le p(|x|)$ for some polynomial $p$). For $V$ to be a verifier, it must satisfy the following two requirements:

1. Completeness: If $x \in P$, then there exists a witness $y$ (with polynomially bounded length) such that $V(x, y) = 1$, that is, $V$ accepts when given input $x$ and $y$.
2. Soundness: If $x \not\in P$, then $V(x, y) = 0$, that is, $V$ rejects for any witness $y$.

In addition, $V$ must run in time polynomial in $|x|$.

Now, notice that, in this setting, $\mathbf{P} \subseteq \mathbf{NP}$ is also a pretty basic fact: Any TM solving a problem $P \in \mathbf{P}$ in polynomial time can be made a verifier simply by giving it the empty string as witness.

On the other hand, $\mathbf{coNP}$ is the set of problems such that their complement is in $\mathbf{NP}$. If $P \in \mathbf{P}$, then its complement $\bar{P}$ is also in $\mathbf{P} \subseteq \mathbf{NP}$ (see also Alex Grilo's answer). It follows that $\bar{P} \in \mathbf{coNP}$.