Add to Quick Collection
All 34 Results
Showing items 1 - 15 of 34.
Add All Items to Quick Collection
Source: Прикладная дискретная математика. 2025. № 69. С. 121-128
Type: статьи в журналах
Date: 2025
Description:
Изучается генерическая сложность двух вариантов проблемы о 3-раскраске графов: проблема распознавания и проблема поиска 3-раскраски графа. Для обеих проблем эффективных полиномиальных алгоритмов неизв
... More
Source: Прикладная дискретная математика. 2025. № 67. С. 110-117
Type: статьи в журналах
Date: 2025
Description:
Изучается вычислительная сложность проблемы проверки разрешимости систем уравнений над бициклическим моноидом. Этот моноид, помимо теоретического значения в топологии и теории полугрупп, имеет приложе
... More
Source: Прикладная дискретная математика. 2024. № 63. С. 109-116
Type: статьи в журналах
Date: 2024
Description:
В рамках генерического подхода изучается поведение алгоритмов на типичных (почти всех) входах, а остальные входы игнорируются. А. Мясниковым и автором ранее был предложен метод генерической амплификац
... More
Source: Прикладная дискретная математика. 2024. № 65. С. 110-117
Type: статьи в журналах
Date: 2024
Description:
Изучается генерическая сложность проблемы вычисления функции Эйлера, имеющей важное значение для современной криптографии. Например, на предположении о её трудноразрешимости основывается криптостойкос
... More
Source: Прикладная дискретная математика. 2024. № 66. С. 116-122
Type: статьи в журналах
Date: 2024
Description:
Изучается генерическая сложность проблемы дискретного логарифма в последовательностях Люка. Эта проблема была использована в 1990-е годы новозеландским криптографом П. Смитом для создания аналога клас
... More
Source: Прикладная дискретная математика. 2024. № 64. С. 72-78
Type: статьи в журналах
Date: 2024
Description:
Изучается генерическая сложность проблемы проверки совместности систем уравнений над натуральными числами со сложением. Доказывается NP-полнота этой проблемы, предлагается полиномиальный генерический
... More
Source: Прикладная дискретная математика. 2023. № 62. С. 119-123
Type: статьи в журналах
Date: 2023
Description:
Изучается генерическая сложность проблемы извлечения квадратного корня по простому модулю. Вопрос о вычислительной сложности этой проблемы до сих пор открыт. Однако известны алгоритмы (например, алгор
... More
Source: Прикладная дискретная математика. 2023. № 60. С. 114-119
Type: статьи в журналах
Date: 2023
Description:
Изучается генерическая сложность проблемы кластеризации графов с ограничением p на размеры кластеров при p > 3. В этой задаче структура взаимосвязей объектов задаётся с помощью графа, вершины которого
... More
Source: Прикладная дискретная математика. 2023. № 61. С. 121-126
Type: статьи в журналах
Date: 2023
Description:
Изучается генерическая сложность проблемы факторизации целых чисел. Данная проблема, восходящая ещё к Гауссу, имеет важное значение для современной криптографии. Например, на предположении о её трудно
... More
Source: Прикладная дискретная математика. 2022. № 57. С. 91-97
Type: статьи в журналах
Date: 2022
Description:
Изучается генерическая сложность проблемы кластеризации графов с ограничениями на число кластеров. В этой проблеме структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответств
... More
Source: Прикладная дискретная математика. 2022. № 55. С. 95-101
Type: статьи в журналах
Date: 2022
Description:
Проблема вхождения в конечно порождённую подгруппу (подполугруппу) для групп (полугрупп) является классической алгоритмической проблемой в алгебре, активно изучаемой многие десятилетия. Уже для достат
... More
Source: Прикладная дискретная математика. 2022. № 58. С. 105-111
Type: статьи в журналах
Date: 2022
Description:
NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проб
... More
Source: Прикладная дискретная математика. 2021. № 51. С. 120-128
Type: статьи в журналах
Date: 2021
Description:
Изучается генерическая сложность проблемы изоморфизма конечных полугрупп. В этой проблеме по любым двум полугруппам одинакового порядка, заданным таблицами умножения, требуется определить, являются ли
... More
Source: Прикладная дискретная математика. Приложение. 2021. № 14. С. 178-180
Type: статьи в журналах
Date: 2021
Description:
Изучается генерическая сложность проблемы изоморфизма конечных полугрупп: по любым двум полугруппам одинакового порядка, заданным таблицами умножения, требуется определить, являются ли они изоморфными
... More
Source: Прикладная дискретная математика. 2021. № 53. С. 120-126
Type: статьи в журналах
Date: 2021
Description:
Изучается генерическая сложность проблемы распознавания гамильтоновых путей в конечных графах. Путь в графе называется гамильтоновым, если он проходит через все вершины ровно по одному разу. Доказывае
... More
