---
title: "A Library of Languages"
source: https://www.jemoka.com/posts/kbha_library_of_languages/
---

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)?
This is in both NP and coNP
But, PERFECT-MATCHING is in \(P\)
Yet, with a randomized algorithm, PERFECT-MATCHING can be solved in parallel time \(O\qty(\log^{2} n)\).
NP trivial I hand you the matching
Not Hall&rsquo;s Theorem Sufficient: Suppose \(S \subseteq U\), consider \(N\qty(S) \subseteq V\), the neighborhood of \(S\) is \(|N(s)|&lt; |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&rsquo;s Theorem Necessary: if \(G = \qty(U, V, E)\) has no perfect matching, then such an \(S\) from Not Hall&rsquo;s Theorem must exist.
PRIMES &ldquo;very prime has a succinct certificate&rdquo;
\begin{equation} \text{PRIMES} : \qty {A \mid A\text{ is prime}} \end{equation}
The certificate?
\begin{equation} A \text{ prime} \Leftrightarrow \exists 1 &lt; b &lt; 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]\)
