Matrix Decomposition Problem is Complete for the Average Case
- Yuri Gurevich
FOCS'90, 31st Annual Symposium on Foundations of Computer Science IEEE Computer Society Press, 1990, 802-811. |
The first algebraic average-case complete problem is presented. It is arguably the simplest natural average-case complete problem to date.