Статья: О ГЕНЕРИЧЕСКОЙ СЛОЖНОСТИ РЕШЕНИЯ УРАВНЕНИЙ НАД НАТУРАЛЬНЫМИ ЧИСЛАМИ СО СЛОЖЕНИЕМ

Скачать

Изучается генерическая сложность проблемы проверки совместности систем уравнений над натуральными числами со сложением. Доказывается NP-полнота этой проблемы, предлагается полиномиальный генерический алгоритм её решения. Доказывается, что при Р ≠ NP и Р = ВРР для проблемы проверки совместности систем уравнений над натуральными числами с нулём не существует сильно генерического полиномиального алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему.

Информация о документе

Формат документа: PDF
Кол-во страниц: 1 страница
Загрузил(а): РЫБАЛОВ Александр Николаевич
Лицензия: —
Доступ: Всем
Просмотров: 2

Информация о статье

ISSN: 2071-0410
EISSN: 2311-2263
Префикс DOI: 10.17223/20710410/64/6
Журнал: ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
Год публикации: 2024
Автор(ы): РЫБАЛОВ А. Н.
Ключевые фразы: ГЕНЕРИЧЕСКАЯ СЛОЖНОСТЬ, ЛИНЕЙНЫЕ УРАВНЕНИЯ, НАТУРАЛЬНЫЕ ЧИСЛА
УДК: 510.52. Сложность алгоритмов

Ранее вы смотрели (10)

01. Книга: Конструкции, или почему не ломаются вещи

02. Статья: ОПРЕДЕЛЕНИЕ СТЕПЕНИ ГОТОВНОСТИ УЧИТЕЛЕЙ ФИЗИЧЕСКОЙ КУЛЬТУРЫ ДОШКОЛЬНЫХ ОБРАЗОВАТЕЛЬНЫХ УЧРЕЖДЕНИЙ К РЕАЛИЗАЦИИ ФИЗИЧЕСКОГО ВОСПИТАНИЯ С ДЕТЬМИ С ОГРАНИЧЕННЫМИ ВОЗМОЖНОСТЯМИ ЗДОРОВЬЯ

03. Книга: Статистический анализ основных показателей здоровья населения и деятельности здравоохранения

04. Статья: Определение основных технических параметров проектируемой сверлильной машины с автоматической подачей

05. Книга: Малая бытовая электроника

06. Статья: АКСИАЛЬНО-ВЕКТОРНЫЙ ФОРМФАКТОР НУКЛОНА В МОДЕЛЯХ АДС/КХД

07. Книга: Карданная передача

08. Книга: КОМБИНИРОВАННЫЕ МЕТОДЫ ОБРАБОТКИ В МАШИНОСТРОЕНИИ

09. Статья: АЛГОРИТМ ВЫЧИСЛЕНИЯ БОКОВОГО ОТКЛОНЕНИЯ С ИСПОЛЬЗОВАНИЕМ СИСТЕМЫ ТЕХНИЧЕСКОГО ЗРЕНИЯ И ЦИФРОВОЙ КАРТЫ ДОРОГ

10. Статья: УЧАСТНИКИ ДЕЛА О БАНКРОТСТВЕ: КТО ЕСТЬ КТО?