On the complexity of computing bilinear forms with {0, 1} constants

摘要

An important class of problems in arithmetic complexity is that of computing a set of bilinear forms, which includes many interesting problems such as the multiplication problems of matrices and polynomials. Recently, this class has been given considerable attention and several interesting results have emerged. However, most of the important issues remain unresolved and the general problem seems to be very difficult. In this paper, we consider one of the simplest cases of the general problem, namely evaluation of bilinear forms with {0, 1} constants, and prove that fording the optimal number of multiplications or the optimal number of additions is NP-hard. We discuss several related problems.