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

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

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

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

Том: 11

Номер: 4

Год: 2004

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

Издательство:

Местоположение издательства:

URL:

Проекты:

DOI:

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

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

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

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

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

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

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

Публикация в печати: 0