A Library of Languages — Jemoka Knowledge Base

PERFECT-MATCHING Given a bipartite graph G = \left(U,V,E\right), 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\left(\log^{2} n\right). NP trivial I hand you the matching Not Hall’s Theorem Sufficient: Suppose S \subseteq U, consider N\left(S\right) \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 = \left(U, V, E\right) 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} : \left\{A \mid A\text{ is prime}\right\} \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} = \left{X, A, B \mid \text{X has a prime factor \in [A,B]}\right} \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]