О генерической сложности решения уравнений над натуральными числами со сложением

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

Add to "Quick Collection"

Description	Size	Format
О генерической сложности решения уравнений над натуральными числами со сложением	618 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/64/6

Title: О генерической сложности решения уравнений над натуральными числами со сложением
Title: On the generic complexity of solving equations over natural numbers with addition
Creator: Рыбалов, Александр Николаевич
Date: 2024
DOI: 10.17223/20710410/64/6
Description: Изучается генерическая сложность проблемы проверки совместности систем уравнений над натуральными числами со сложением. Доказывается NP-полнота этой проблемы, предлагается полиномиальный генерический алгоритм её решения. Доказывается, что при Р = NP и Р = ВРР для проблемы проверки совместности систем уравнений над натуральными числами с нулём не существует сильно генерического полиномиального алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему.

Created: 25-09-2024

251 Visitors

200 Hits

60 Downloads

Журналы ТГУ О генерической сложности решения уравнений над натуральными числами со сложением