Polynomial Identity Testing

Polynomial identity testing is the decision problem of whether an arithmetic expression computes the zero polynomial. A test may inspect the circuit or formula, or may obtain information only from evaluations. For noncommutative arithmetic formulas, a matrix hitting point is a single tuple of square matrices on which every nonzero formula in a specified class is nonzero. A hitting list instead permits a different successful tuple for each formula.