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

Изучается генерическая сложность проблемы проверки совместности систем уравнений над натуральными числами со сложением. Доказывается $\text{NP}$-полнота этой проблемы, предлагается полиномиальный генерический алгоритм её решения. Доказывается, что при $\text{P} \neq \text{NP}$ и $\text{P} = \text{BPP}$ для проблемы проверки совместности систем уравнений над натуральными числами с нулём не существует сильно генерического полиномиального алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему.