Threshold Circuits for Iterated Matrix Product and Powering
Carlo Mereghetti, Beatrice Palano (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
The complexity of computing, via threshold circuits, the and of fixed-dimension matrices with integer or rational entries is studied. We call these two problems and , respectively, for short. We prove that: (i) For , does not belong to , unless .newline (ii) For : belongs to while, for , does not belong to , unless . (iii) For any , belongs to .