Том 11, серия 1, номер 4, 2004 г., Стр. 44-55
УДК 519.16
А. А. Семенов
О сложности обращения дискретных функций из одного класса
Аннотация:
Рассматривается обращение некоторых дискретных функций, встречающихся в криптографии. Устанавливается сводимость по Куку задач обращения таких функций к задачам, принадлежащим NP$\cap$ co-NP. Изучаются конъюнктивные нормальные формы (КНФ), выполнимые в точности на одном наборе. Показывается, что задача поиска выполняющего набора в таких КНФ сводится по Куку к проблеме из NP$\cap$ co-NP, тогда как задача распознавания таких КНФ является co-NP трудной.
Семенов А. А. 1
1. Институт динамики систем и теории управления СО РАН,
ул. Лермонтова, 134, 664033 Иркутск, Россия
Статья поступила 15 апреля 2004 г.
Исправленный вариант — 23 августа 2004 г.
