ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
1998, ТОМ 4, ВЫПУСК 2, СТР. 511-523

О системах линейных уравнений с $k$-значными неизвестными, имеющих полиномиальную трудоемкость решения

А. Н. Велигура

Аннотация

Посмотреть как HTML    Посмотреть как рисунок    Посмотреть в формате LaTeX

Описан класс совместных систем $m$ линейных уравнений с $n$ $k$-значными неизвестными, имеющих полиномиальную трудоемкость решения, и для числа $\nu$_k(n,m) систем класса найдены точная и асимптотические формулы. В частности, при $n,m\; \to \; \infty$ так, что $m/n=(1-1/k)+\; \omega \; n-1/2$, где $\omega \; \to \; +\; \infty$, почти все совместные системы с матрицей с общим положением столбцов решаются за полиномиальное время.

Постскрипт статьи (57 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/98/982/98203h.htm
Изменения вносились 24 апреля 2000 г.