Problem $4$

Let us define the complexity class co$-$NP to contain all the decision problems whose complement is in NP$.$ In particular, this class will contain all the decision problems for which there is an efficient verifier for the NO instances. $($Note that NP contains all the decision problems for which there is an efficient verifier for the YES instances.$)$

For instance, consider the following problem:

CONNECTED: Given an undirected graph $\backslash ($ G $\backslash )$ on $\backslash ($ n $\backslash )$ vertices, is $\backslash ($ G $\backslash )$ connected?

For this decision problem, the NO$-$instances contain all the inputs $($graphs$)$ which have more than $1$ connected component. Therefore, a certificate for the NO$-$instances can be a pair of vertices $\backslash ($ u$,$ v $\backslash )$ such that there is no path from $\backslash ($ u $\backslash )$ to $\backslash ($ v $\backslash )$ in $\backslash ($ G $\backslash ).$ This can be efficiently $($in $\backslash ($ O$($m$+$n$)\backslash )$ time$)$ verified using BFS$.$ Therefore, CONNECTED $\backslash (\backslash$in $\backslash )$ co$-$NP$.$

Show that the complexity class co$-$NP contains the complexity class P $,$ i$.$e$.,\backslash (\backslash$mathrm$\{$P$\}\backslash$subseteq $\backslash )$ co$-$NP$.$ The proof should show that any decision problem in P has a short certificate for the NO instances that can be verified efficiently.