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

doi:10.17223/20710410/70/6

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

Add to "Quick Collection"

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

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

#конечные алгебраические системы

#уравнения

Title: О генерической сложности решения уравнений в конечных предикатных алгебраических системах
Title: Оn generic complexity оf solving оf equations in finite predicate algebraic structures
Creator: Рыбалов, Александр Николаевич
Date: 2025
DOI: 10.17223/20710410/70/6
Description: Изучается генерическая сложность двух вариантов проблемы решения уравнений без констант над конечными предикатными алгебраическими системами: распознавания разрешимости и поиска решения. Для обеих проблем во многих случаях неизвестно эффективных полиномиальных алгоритмов. Предлагается полиномиальный генерический алгоритм для проблемы распознавания разрешимости. С другой стороны, для проблемы поиска решения доказывается, что если для нее нет полиномиального вероятностного алгоритма, то существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Полученный результат является теоретическим обоснованием возможных приложений проблемы поиска решения в криптографии, где нужно, чтобы проблема взлома криптоалгоритма была трудной для почти всех входов.

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

Created: 10-12-2025

3 Visitors

3 Hits

0 Downloads

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