Пусть квадрат вещественной матрицы и два вектора и длины такие, что
Решение для помощью стандартного исключения Гаусса дает совокупную сложность почти . Однако существуют случаи, когда решение (или -приближенное решение) для стоит , например, системы, в которых является симметричной и диагонально доминирующей матрицей (например, лапласианом) [1].
Какие другие семейства линейных систем (т.е. матриц) допускают линейные (или нетривиальные поли (n)) временные решения? Если мы рассмотрим конечные поля вместо реальных матриц, есть ли там семейства матриц, которые допускают почти линейные временные решения?
[1] http://www.cs.yale.edu/homes/spielman/Research/linsolve.html