Страница публикации

О сложности обращения дискретных функций из одного класса

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Семенов А.А.

Журнал: Дискретный анализ и исследование операций. Сер. 1

Язык публикации: russian

Том: 11

Номера страниц: 44-55

Количество страниц: 12

Номер: 4

Год публикации: 2004

Отчетный год: 2004

Аннотация: Рассматривается обращение некоторых дискретных функций, встречающихся в криптографии. Устанавливается сводимость по Куку задач обращения таких функций к задачам, принадлежащим NP∩co-NP. Изучаются конъюнктивные нормальные формы (КНФ), выполнимые в точности на одном наборе. Показывается, что задача поиска выполняющего набора в таких КНФ сводится по Куку к проблеме из NP∩co-NP, тогда как задача распознавания таких КНФ является co-NP трудной. Библ. 10.

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет