The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension k×k matrices with integer or rational entries is studied. We call these two problems IMPk and MPOWk, respectively, for short. We prove that: (i) For k≥2, IMPk does not belong to TC0, unless TC0 = NC1. (ii) For stochastic matrices: IMP2 belongs to TC0 while, for k≥3, IMPk does not belong to TC0, unless TC0 = NC1. (iii) For any k, MPOWk belongs to TC0.
Threshold circuits for iterated matrix product and powering / C. Mereghetti, B.S. Palano. - In: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS. - ISSN 0988-3754. - 34:1(2000), pp. 39-46. ((Intervento presentato al 6. convegno Italian Conference on theoretical Computer Science tenutosi a Prato nel 1998.
Threshold circuits for iterated matrix product and powering
C. Mereghetti
;B.S. PalanoUltimo
2000
Abstract
The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension k×k matrices with integer or rational entries is studied. We call these two problems IMPk and MPOWk, respectively, for short. We prove that: (i) For k≥2, IMPk does not belong to TC0, unless TC0 = NC1. (ii) For stochastic matrices: IMP2 belongs to TC0 while, for k≥3, IMPk does not belong to TC0, unless TC0 = NC1. (iii) For any k, MPOWk belongs to TC0.
| File | Dimensione | Formato | |
|---|---|---|---|
|
pubblicato.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
157.49 kB
Formato
Adobe PDF
|
157.49 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
