| Popis: |
Генерический подход к алгоритмическим проблемам был предложен Мясниковым, Каповичем, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. В работе изучается генерическая сложность проблемы представимости натуральных чисел суммой двух квадратов. Данная проблема, восходящая ещё к Ферма и Эйлеру, тесно связана с проблемой факторизации целых чисел и проблемой распознавания квадратичности вычетов по составным модулям, для решения которых не известно эффективных алгоритмов. Доказывается, что, при условии трудно- разрешимости этой проблемы в худшем случае и P = BPP, для её решения не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность относительных плотностей которого при увеличении размера экспоненциально быстро сходится к единице. Для доказательства используется метод генерической амплификации, который позволяет строить генерически трудные проблемы из проблем, трудных в худшем случае. Основным ингредиентом метода является объединение эквивалентных входов в достаточно большие множества. Эквивалентность входов означает, что рассматриваемая проблема на них решается одинаково. |
