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

Рыбалов, Александр Николаевич

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

Дата публикации: 2024

Дата публикации в реестре: 2024-10-01T21:22:32Z

Аннотация:

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

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

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2024. № 64. С. 72-78