Reaching matrix period is NP-complete

Rok, strany: 1997, 81 - 88

A problem connected with periodicity of matrix sequences and vector orbits in a fuzzy algebra is studied. The question is how to decide whether the matrix period $per(A)$ of a given matrix $A$ can be reached by the vector orbit period $per(A)$ for some vector $x$. It is proved that the problem is NP-complete, in spite of the fact that the matrix period $per(A)$ is the least common multiple of all vector orbit periods and the matrix period, as well as the individual orbit periods, can be computed in a polynomial time.

ISO 690:

Gavalec, M. 1997. Reaching matrix period is NP-complete. In Tatra Mountains Mathematical Publications, vol. 12, no.3, pp. 81-88. 1210-3195.

APA:

Gavalec, M. (1997). Reaching matrix period is NP-complete. Tatra Mountains Mathematical Publications, 12(3), 81-88. 1210-3195.