# P is contained in NP ∩ Co-NP?

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.

• Perhaps you would benefit from trying it first on a sample problem. For example, how would you show that the Euler-circuit problem (which is in P) is in NP and in coNP? – Shaull May 2 '13 at 11:17

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

• I think the OP is also looking for the direction $P \subseteq NP$. Consider adding it to your answer. – Shaull May 2 '13 at 11:20

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.

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