|
Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)
Теоретические основы прикладной дискретной математики
Двоичные решения для больших систем линейных уравнений
А. В. Селиверстов Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, г. Москва, Россия
Аннотация:
Понятие генерической вычислительной сложности распространено на обобщённые регистровые машины над упорядоченным полем. В этом случае машина на каждом входе останавливается и почти на каждом входе даёт содержательный ответ, но может отказаться от вычисления посредством явного уведомления об этом, иными словами, существует особое неопределённое состояние остановки. При этом машина не делает ошибок. Предложен генерический алгоритм полиномиального времени для распознавания систем линейных уравнений без какого-либо двоичного решения, когда число уравнений $m$ близко к числу неизвестных $n$. Более точно — требуется выполнение двух условий. Во-первых, выполнено неравенство $2n\geqslant (n-m+1)(n-m+2)$. Такие системы называются большими, поскольку число уравнений близко к числу неизвестных. Во-вторых, выполнены некоторые предположения общности системы уравнений. Наш подход основан на поиске положительно определённой квадратичной формы среди множества форм, зависящих от параметров. С другой стороны, найден контрпример, показывающий неприменимость этого метода для проверки отсутствия двоичного решения у одного уравнения.
Ключевые слова:
двоичное решение, линейное уравнение, обобщённая регистровая машина, вычислительная сложность.
Образец цитирования:
А. В. Селиверстов, “Двоичные решения для больших систем линейных уравнений”, ПДМ, 2021, № 52, 5–15
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm735 https://www.mathnet.ru/rus/pdm/y2021/i2/p5
|
Статистика просмотров: |
Страница аннотации: | 211 | PDF полного текста: | 73 | Список литературы: | 29 |
|