|
Дискретный анализ и исследование операций, сер. 1, 2004, том 11, выпуск 4, страницы 44–55
(Mi da119)
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
О сложности обращения дискретных функций
из одного класса
А. А. Семенов Институт динамики систем и теории управления СО РАН
Аннотация:
Рассматривается обращение некоторых дискретных функций, встречающихся в криптографии. Устанавливается сводимость по Куку задач обращения таких функций к задачам, принадлежащим NP$\cap$co-NP. Изучаются конъюнктивные нормальные формы (КНФ), выполнимые в точности на одном наборе. Показывается, что задача поиска выполняющего набора в таких КНФ сводится по Куку к проблеме из NP$\cap$co-NP, тогда как задача распознавания таких КНФ является co-NP трудной.
Статья поступила: 15.04.2004 Переработанный вариант: 23.08.2004
Образец цитирования:
А. А. Семенов, “О сложности обращения дискретных функций
из одного класса”, Дискретн. анализ и исслед. опер., сер. 1, 11:4 (2004), 44–55
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da119 https://www.mathnet.ru/rus/da/v11/s1/i4/p44
|
Статистика просмотров: |
Страница аннотации: | 474 | PDF полного текста: | 129 | Список литературы: | 58 |
|