A. O. Savinskii, “The complexity of ratings matrices completion problem for recommendation systems”, Intelligent systems. Theory and applications, 2015, Volume 19, Issue 3,Pages <nobr>5

Part 1. General problems of the intellectual systems theory

The complexity of ratings matrices completion problem for recommendation systems

A. O. Savinskii

Abstract: A mathematical model of recommendation systems is constructed. Estimates of users types number in matrix of users is found. It is found out, that problems of search matrix of users and enumeration of them in general case are a NPhardness problems. Furthermore, polynomial algorithm for search matrix of users when the user types number is two is provided.

Keywords: recommendation systems, matrix completion, search matrix of users, enumeration of matrices of users.