On the Complexity of Tensor Formulae

We consider formulae on base of sum, product, and tensor product of matrices . In particular, we consider matrices over the Boolean semi-ring B = (f0; 1g; _; ^) and over the two-element eld F 2 = (f0; 1g; +; ). The evaluation problem for tensor formulae over a certain semi-ring S (denoted TEP S ) is the set of formulae that evaluate to 1 over S. We prove: (1) TEP B and TEP F 2 are complete for NP and P , respectively, under polynomial time reductions. (2) When restricted to formulae containing only small subformulae, these problems are complete for LOGCFL and LOGCFL, respectively, under log-space reductions. Restriction to formulae without tensor products leads to problems that are complete for NL and L, respectively. We demonstrate the strength of these characterizations by giving a unied proof for the inclusions NP =poly P=poly, LOGCFL=poly LOGCFL=poly, and NL=poly L=poly. 1 Introduction There are several results in the literature demonstrating that Boolean c..