Matrix decomposition problem is complete for the average case
Yuri G. Gurevich · 2002
The first algebraic average-case complete problem is presented. The focus of attention is the modular group, i.e., the multiplicative group SL/sub 2/(Z) of two-by-two integer matrices of determinant 1. By default, in this study matrices are elements of the modular group. The problem is arguably the simplest natural average-case complete problem to date.>