Suggest edit — A Library of Languages

Title

Name

Note

---
title: "A Library of Languages"
type: concept
related: [Conp, Non Polynomial Time, Randomized Algorithum]
source: https://www.jemoka.com/posts/kbha_library_of_languages/
confidence: high
status: active
---

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