Аннотация:
Понятие генерической вычислительной сложности распространено на обобщённые регистровые машины над упорядоченным полем. В этом случае машина на каждом входе останавливается и почти на каждом входе даёт содержательный ответ, но может отказаться от вычисления посредством явного уведомления об этом, иными словами, существует особое неопределённое состояние остановки. При этом машина не делает ошибок. Предложен генерический алгоритм полиномиального времени для распознавания систем линейных уравнений без какого-либо двоичного решения, когда число уравнений mm близко к числу неизвестных nn. Более точно — требуется выполнение двух условий. Во-первых, выполнено неравенство 2n⩾(n−m+1)(n−m+2). Такие системы называются большими, поскольку число уравнений близко к числу неизвестных. Во-вторых, выполнены некоторые предположения общности системы уравнений. Наш подход основан на поиске положительно определённой квадратичной формы среди множества форм, зависящих от параметров. С другой стороны, найден контрпример, показывающий неприменимость этого метода для проверки отсутствия двоичного решения у одного уравнения.
\RBibitem{Sel21}
\by А.~В.~Селиверстов
\paper Двоичные решения для больших систем линейных уравнений
\jour ПДМ
\yr 2021
\issue 52
\pages 5--15
\mathnet{http://mi.mathnet.ru/pdm735}
\crossref{https://doi.org/10.17223/20710410/52/1}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm735
https://www.mathnet.ru/rus/pdm/y2021/i2/p5
Эта публикация цитируется в следующих 9 статьяx:
A. V. Seliverstov, O. A. Zverkov, “Lower Bounds for the Rank of a Matrix with Zeros and Ones outside the Leading Diagonal”, Program Comput Soft, 50:2 (2024), 202
A. V. Seliverstov, O. A. Zverkov, “Lower bounds for the rank of a matrix with zeros and ones outside the leading diagonal”, Programmirovanie, 2024, № 2, 100
А. А. Бойков, А. В. Селиверстов, “О кубе и проекциях подпространства”, Вестн. Удмуртск. ун-та. Матем. Мех. Компьют. науки, 33:3 (2023), 402–415
O. A. Zverkov, A. V. Seliverstov, “Effective Lower Bounds on the Matrix Rank and Their Applications”, Programmirovanie, 2023, № 5, 79
А. В. Селиверстов, “Обобщение задачи о сумме подмножеств и кубические формы”, Ж. вычисл. матем. и матем. физ., 63:1 (2023), 51–60; A. V. Seliverstov, “Generalization of the subset sum problem and cubic forms”, Comput. Math. Math. Phys., 63:1 (2023), 48–56
O. A. Zverkov, A. V. Seliverstov, “Effective Lower Bounds on the Matrix Rank and Their Applications”, Program Comput Soft, 49:5 (2023), 441
А. Н. Рыбалов, “О генерической сложности проблемы вхождения для полугрупп целочисленных матриц”, ПДМ, 2022, № 55, 95–101
И. В. Латкин, А. В. Селиверстов, “О вычислениях над упорядоченными кольцами”, Сиб. электрон. матем. изв., 19:2 (2022), 1054–1076
Александр Владиславович Селиверстов, Математические основы информатики и информационно-коммуникационных систем, 2021, 262