Reminder: This post contains 1347 words
· 4 min read
· by Xianbin
Random NC: it is used to define a problem that can be solved in polylog time by a randomized parallel algorithm using a polynomial number of processors.
\(\textbf{Lemma}[\textup{Schwartz–Zippel}]\). Let \(\mathbb{F}\) denote a field and let \(f(x_1,\ldots,x_n) \in \mathbb{F}[x_1,\ldots,x_n]\) be a nonzero multivariate polynomial of degree \(d\). Let \(S\subseteq \mathbb{F}\) be a finite set. Then, we have
\[\mathbb{P}[f(a_1,\ldots,a_n)=0] \leq \frac{d}{\lvert S \rvert}\]
The degree of a polynomial is the largest degree of its monomials. For example,
\[f(x_1,x_2) = x_1x_2^2 + 1\]
has degree 3.
There, we set \(f(x) = x_1^d + x_2+\ldots\). After uniformly at random selecting from the finite set, the probability that they are the root is very small, at most \(d/\lvert S \rvert\).
Given an undirected graph \(G=(V, E)\), its Tutte matrix \(T\) is the \(n\times n\) symbolic matrix as follows.
Let \((i,j)\in E\) denote the edge in \(G\).
\[M_{i,j} : =
\begin{cases}
x_{i,j}, && i<j \\
-x_{i,j}, && i>j \\
0, && \text{Otherwise}
\end{cases}\]
We can show that \(M\) is skew-symmetric, i.e.,
\[M^T = - M\]
\(\textbf{Lemma}\)[Tutte’s Perfect Matching Lemma] Let \(M\) be the Tutte matrix of an undirected graph \(G=(V, E)\). We have
\[\text{det}(M) \not = 0\]
if and only if \(G\) has a perfect matching.
Reference
[1]. Karp, R.M., Upfal, E. and Wigderson, A., 1985, December. Constructing a perfect matching is in random NC. In Proceedings of the seventeenth annual ACM symposium on Theory of computing (pp. 22-32).