Профиль » Публикация

Аннотация Описан класс совместных систем m линейных уравнений с n k-значными неизвестными, имеющих полиномиальную трудоемкость решения, и для числа ν k(n,m) систем класса найдены точная и асимптотические формулы. В частности, при n,m → ∞ так, что m/n=(1-1/k)+ ω n-1/2, где ω → + ∞, почти все совместные системы с матрицей с общим положением столбцов решаются за полиномиальное время.