Двоичные решения для больших систем линейных уравнений

doi:10.17223/20710410/52/1

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Двоичные решения для больших систем линейных уравнений	1 MB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/52/1

#двоичное решение

#линейные уравнения

#обобщенная регистровая машина

#вычислительная сложность

Title: Двоичные решения для больших систем линейных уравнений
Title: Binary solutions to large systems of linear equations
Creator: Селиверстов, Александр Владиславович
Date: 2021
DOI: 10.17223/20710410/52/1
Description: Понятие генерической вычислительной сложности распространено на обобщённые регистровые машины над упорядоченным полем. В этом случае машина на каждом входе останавливается и почти на каждом входе даёт содержательный ответ, но может отказаться от вычисления посредством явного уведомления об этом, иными словами, существует особое неопределённое состояние остановки. При этом машина не делает ошибок. Предложен генерический алгоритм полиномиального времени для распознавания систем линейных уравнений без какого-либо двоичного решения, когда число уравнений m близко к числу неизвестных n. Более точно - требуется выполнение двух условий. Во-первых, выполнено неравенство 2n ≥(n-m+1)(n-m+2). Такие системы называются большими, поскольку число уравнений близко к числу неизвестных. Во-вторых, выполнены некоторые предположения общности системы уравнений. Наш подход основан на поиске положительно определённой квадратичной формы среди множества форм, зависящих от параметров. С другой стороны, найден контрпример, показывающий неприменимость этого метода для проверки отсутствия двоичного решения у одного уравнения.