Прикладная дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Прикладная дискретная математика, 2021, номер 52, страницы 5–15
DOI: https://doi.org/10.17223/20710410/52/1
(Mi pdm735)
 

Эта публикация цитируется в 9 научных статьях (всего в 9 статьях)

Теоретические основы прикладной дискретной математики

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

А. В. Селиверстов

Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, г. Москва, Россия
Список литературы:
Аннотация: Понятие генерической вычислительной сложности распространено на обобщённые регистровые машины над упорядоченным полем. В этом случае машина на каждом входе останавливается и почти на каждом входе даёт содержательный ответ, но может отказаться от вычисления посредством явного уведомления об этом, иными словами, существует особое неопределённое состояние остановки. При этом машина не делает ошибок. Предложен генерический алгоритм полиномиального времени для распознавания систем линейных уравнений без какого-либо двоичного решения, когда число уравнений $m$ близко к числу неизвестных $n$. Более точно  — требуется выполнение двух условий. Во-первых, выполнено неравенство $2n\geqslant (n-m+1)(n-m+2)$. Такие системы называются большими, поскольку число уравнений близко к числу неизвестных. Во-вторых, выполнены некоторые предположения общности системы уравнений. Наш подход основан на поиске положительно определённой квадратичной формы среди множества форм, зависящих от параметров. С другой стороны, найден контрпример, показывающий неприменимость этого метода для проверки отсутствия двоичного решения у одного уравнения.
Ключевые слова: двоичное решение, линейное уравнение, обобщённая регистровая машина, вычислительная сложность.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-29-13037
Исследование выполнено при финансовой поддержке РФФИ, проект №18-29-13037.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.161
Образец цитирования: А. В. Селиверстов, “Двоичные решения для больших систем линейных уравнений”, ПДМ, 2021, № 52, 5–15
Цитирование в формате AMSBIB
\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:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Статистика просмотров:
    Страница аннотации:211
    PDF полного текста:73
    Список литературы:29
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024