= Solution
Writing $\mathrm{PTime}$ as <P> and $\mathrm{co\text{-}PTime}$ as <co-P>, the known relationships among the four <complexity classes> are
$$
\boxed{\mathrm P=\mathrm{co\text{-}P},\qquad
\mathrm P\subseteq\mathrm{NP},\qquad
\mathrm P\subseteq\mathrm{co\text{-}NP}.}
$$
The equality supplies both inclusions between <P> and <co-P>, and it also gives <co-P> $\subseteq$ <NP> and <co-P> $\subseteq$ <co-NP>.
For the equality, a deterministic <polynomial-time algorithm> halts on every <input>; interchange its accepting and rejecting outcomes to decide the <complement of a set> in the same <polynomial time>. For <P> $\subseteq$ <NP>, a <Nondeterministic Turing machine> can simply make no choices and follow the deterministic computation. Finally, if $A\in\mathrm P$, then $\overline A\in\mathrm P\subseteq\mathrm{NP}$, whence $A\in\mathrm{co\text{-}NP}$ by the definition of <co-NP>.
Neither <NP> $\subseteq$ <co-NP> nor <co-NP> $\subseteq$ <NP> is known; either would imply equality by taking <complements>. Nor is either inclusion of <P> into <NP> or <co-NP> known to be strict. These unresolved relationships must not be presented as strict separations.
Back to article page
