|
|
Дискретн. анализ и исслед. опер., сер. 1, 2004, том 11, номер 4, страницы 44–55
(Mi da119)
|
 |
|
 |
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
О сложности обращения дискретных функций
из одного класса
А. А. Семенов
Институт динамики систем и теории управления СО РАН
Аннотация:
Рассматривается обращение некоторых дискретных функций, встречающихся в криптографии. Устанавливается сводимость по Куку задач обращения таких функций к задачам, принадлежащим NP$\cap$co-NP. Изучаются конъюнктивные нормальные формы (КНФ), выполнимые в точности на одном наборе. Показывается, что задача поиска выполняющего набора в таких КНФ сводится по Куку к проблеме из NP$\cap$co-NP, тогда как задача распознавания таких КНФ является co-NP трудной.
 Полный текст:
PDF файл (254 kB)
Список литературы:
PDF файл
HTML файл
Реферативные базы данных:
УДК:
519.16
Статья поступила: 15.04.2004
Переработанный вариант: 23.08.2004
Образец цитирования:
А. А. Семенов, “О сложности обращения дискретных функций
из одного класса”, Дискретн. анализ и исслед. опер., сер. 1, 11:4 (2004), 44–55
Цитирование в формате AMSBIB
\RBibitem{Sem04}
\by А.~А.~Семенов
\paper О~сложности обращения дискретных функций
из одного класса
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2004
\vol 11
\issue 4
\pages 44--55
\mathnet{http://mi.mathnet.ru/da119}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2113070}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/da119 http://mi.mathnet.ru/rus/da/v11/s1/i4/p44
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
О. С. Заикин, A. A. Семенов, “Технология крупноблочного параллелизма в SAT-задачах”, Пробл. управл., 1 (2008), 43–50
 -
Семенов А.А., Отпущенников И.В., Кочемазов С.Е., “Пропозициональный подход в задачах тестирования дискретных автоматов”, Современные технологии. Системный анализ. Моделирование, 2009, № 4, 48–56
 -
Игнатьев А.С., Семенов А.А., Хмельнов А.Е., “Использование двоичных диаграмм решений в задачах обращения дискретных функций”, Вестн. Томского гос. ун-та. Управление, вычислительная техника и информатика, 2009, № 1, 115–129
-
Семенов А.А., “Декомпозиционные представления логических уравнений в задачах обращения дискретных функций”, Изв. РАН. Теория и системы управления, 2009, № 5, 47–61
 ; Semenov A.A., “Decomposition representations of logical equations in problems of inversion of discrete functions”, Journal of Computer and Systems Sciences International, 48:5 (2009), 718–731   
|
| Просмотров: |
| Эта страница: | 399 | | Полный текст: | 115 | | Литература: | 43 |
|
Пользовательское соглашение