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

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

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



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






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


ПДМ, 2019, номер 45, страницы 26–32 (Mi pdm668)  

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

О двоичных решениях систем уравнений

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

Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, г. Москва, Россия

Аннотация: Решение называется двоичным, если каждая переменная равна нулю или единице. Известно, что трудно найти двоичное решение системы алгебраических уравнений, коэффициенты которых являются целыми числами с малыми абсолютными значениями. Целью работы является обоснование эффективного вероятностного сведения системы к одному новому уравнению в случае, когда существует небольшая разница между числом двоичных решений первого уравнения и числом двоичных решений всей системы. Более того, если первое уравнение линейное, то существует алгоритм псевдополиномиального времени для проверки правильности такого сведения к новому уравнению в общем случае.

Ключевые слова: алгебраическое уравнение, вероятностный алгоритм, вычислительная сложность.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-29-13037_мк
Работа поддержана грантом РФФИ № 18-29-13037.


DOI: https://doi.org/10.17223/20710410/45/3

Полный текст: PDF файл (658 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 511.528

Образец цитирования: А. В. Селиверстов, “О двоичных решениях систем уравнений”, ПДМ, 2019, № 45, 26–32

Цитирование в формате AMSBIB
\RBibitem{Sel19}
\by А.~В.~Селиверстов
\paper О двоичных решениях систем уравнений
\jour ПДМ
\yr 2019
\issue 45
\pages 26--32
\mathnet{http://mi.mathnet.ru/pdm668}
\crossref{https://doi.org/10.17223/20710410/45/3}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm668
  • http://mi.mathnet.ru/rus/pdm/y2019/i3/p26

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:82
    Полный текст:21
    Литература:3
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020