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

doi:10.17223/2226308X/13/33

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

Add to "Quick Collection"

Description	Size	Format
О генерической сложности проблемы представимости натуральных чисел суммой двух квадратов	2 MB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/2226308X/13/33

#генерическая сложность

#суммы квадратов

#Диофантовы уравнения

Title: О генерической сложности проблемы представимости натуральных чисел суммой двух квадратов
Creator: Рыбалов, Александр Николаевич
Date: 2020
DOI: 10.17223/2226308X/13/33
Description: Изучается генерическая сложность проблемы представимости натуральных чисел суммой двух квадратов. Эта проблема, восходящая ещё к Ферма и Эйлеру, тесно связана с проблемами факторизации целых чисел и распознавания квадратичности вычетов по составным модулям, для решения которых не известно эффективных алгоритмов. Доказывается, что, при условии трудноразрешимости этой проблемы в худшем случае и P = BPP, для её решения не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность относительных плотностей которого при увеличении размера экспоненциально быстро сходится к 1.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. Приложение. 2020. № 13. С. 111-113
Language: rus

Created: 08-09-2020

389 Visitors

285 Hits

110 Downloads

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