PERFECT-MATCHING
Given a bipartite graph \(G = \qty(U,V,E)\), is there a perfect matching (a one to one correspondence between \(U\) and \(V\) nodes)?
But, PERFECT-MATCHING is in \(P\)
NP trivial
I hand you the matching
Not Hall’s Theorem
Sufficient: Suppose \(S \subseteq U\), consider \(N\qty(S) \subseteq V\), the neighborhood of \(S\) is \(|N(s)|< |S|\), then there is no perfect matching.
Sketch: suppose for contradiction there is a matching, but there would be not enough space to assign everyone in \(S\) a deduplicated match.
Hall’s Theorem
Necessary: if \(G = \qty(U, V, E)\) has no perfect matching, then such an \(S\) from Not Hall’s Theorem must exist.
PRIMES
“very prime has a succinct certificate”
\begin{equation} \text{PRIMES} : \qty {A \mid A\text{ is prime}} \end{equation}
The certificate?
\begin{equation} A \text{ prime} \Leftrightarrow \exists 1 < b < A : B, B^{2}, \dots, B^{A*2} \not \cong \ \text{mod}\ A \end{equation}
So \(\text{PRIMES} \in \text{NP}\)
FACTORING
\begin{equation} \text{FACTORING} = \qty {X, A, B \mid \text{X has a prime factor $\in [A,B]$}} \end{equation}
\(\text{FACTORING} \in NP\) certificate: just give the prime factor
\(\text{FACTORING} \in \text{coNP}\) certificate: give the prime factorization of \(X\); verifier check that these numbers do multiply to \(x\), check that none of these numbers are in \([A,B]\)