determinent is easy to compute.)If it's 0,then claim that G doesn't have a perfect matching; otherwise claim that G does If G doesn't have a perfect matching,then Det(MG)is a zero polynomial,so whatever(a,..,an)is picked,the algorithm gives the correct answer.If G has a perfect matching,then Det(MG)is a nonzero polynomial,thus by the lemma,a random(a,..,a)is not the root with probability 1-1/n,thus the algorithm outputs the correct answer with high probability. 2.2 Arithmetic circuits and Polynomial ldentity Testing In the previous discussion,we ran into the problem of deciding whether a given polynomial is zero polynomial.This problem is very important on its own,and in this section we will discuss it in the framework of arithmetic circuits.An arithmetic circuit is similar to a Boolean circuit,except to use x and gates instead of AND and OR gates.More precisely,an arithmetic circuit over the field F and the set of variablesx={x1,...,x)is a directed acyclic graph (DAG),with each vertex having in-degree either 0 or 2.Each vertex with in-degree 0 is associated with either a variable from x or a field element from F.Each vertex with in-degree 2 is associated with either a x gate,or a gate. The size of a circuit is the number ofedges.The depth of a circuit is the number ofedges on a longest directed path.(There is one catch here:Sometimes people talk about constant-depth circuits,in which case there is no bound on the in-degree. An arithmetic circuit is an arithmetic formula if the DAG is a tree with the in-degree-0 gates being the leaves. An arithmetic circuit computes a polynomial in a natural way by following the direction of the graph and computation on the gates. Formally,the problem is defined as follows. Problem(Polynomial Identity Testing,or PIT)Given an arithmetic circuit,decide whether it computes the zero polynomial. Note that a polynomial is zero if and only if all its coefficients are zero.It's different than zero as a function,namely zero for all inputs.For example,x2-x takes zero values for all possible x in (0,1), but it's not a zero polynomial.determinent is easy to compute.) If it’s 0, then claim that G doesn’t have a perfect matching; otherwise claim that G does. If G doesn’t have a perfect matching, then Det(MG) is a zero polynomial, so whatever (a1, .., an) is picked, the algorithm gives the correct answer. If G has a perfect matching, then Det(MG) is a nonzero polynomial, thus by the lemma, a random (a1, .., an) is not the root with probability 1-1/n, thus the algorithm outputs the correct answer with high probability. 2.2 Arithmetic circuits and Polynomial Identity Testing In the previous discussion, we ran into the problem of deciding whether a given polynomial is zero polynomial. This problem is very important on its own, and in this section we will discuss it in the framework of arithmetic circuits. An arithmetic circuit is similar to a Boolean circuit, except to use × and + gates instead of AND and OR gates. More precisely, an arithmetic circuit Φ over the field F and the set of variables x = {x1, . . . , xn} is a directed acyclic graph (DAG), with each vertex having in-degree either 0 or 2. Each vertex with in-degree 0 is associated with either a variable from x or a field element from F. Each vertex with in-degree 2 is associated with either a ×gate, or a + gate. The size of a circuit is the number of edges. The depth of a circuit is the number of edges on a longest directed path. (There is one catch here: Sometimes people talk about constant-depth circuits, in which case there is no bound on the in-degree.) An arithmetic circuit is an arithmetic formula if the DAG is a tree with the in-degree-0 gates being the leaves. An arithmetic circuit computes a polynomial in a natural way by following the direction of the graph and computation on the gates. Formally, the problem is defined as follows. Problem (Polynomial Identity Testing, or PIT) Given an arithmetic circuit, decide whether it computes the zero polynomial. Note that a polynomial is zero if and only if all its coefficients are zero. It’s different than zero as a function, namely zero for all inputs. For example, x2 -x takes zero values for all possible x in {0,1}, but it’s not a zero polynomial