RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискретн. анализ и исслед. опер., сер. 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

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. О. С. Заикин, A. A. Семенов, “Технология крупноблочного параллелизма в SAT-задачах”, Пробл. управл., 1 (2008), 43–50  mathnet
    2. Семенов А.А., Отпущенников И.В., Кочемазов С.Е., “Пропозициональный подход в задачах тестирования дискретных автоматов”, Современные технологии. Системный анализ. Моделирование, 2009, № 4, 48–56  elib
    3. Игнатьев А.С., Семенов А.А., Хмельнов А.Е., “Использование двоичных диаграмм решений в задачах обращения дискретных функций”, Вестн. Томского гос. ун-та. Управление, вычислительная техника и информатика, 2009, № 1, 115–129
    4. Семенов А.А., “Декомпозиционные представления логических уравнений в задачах обращения дискретных функций”, Изв. РАН. Теория и системы управления, 2009, № 5, 47–61  zmath; 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  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:369
    Полный текст:106
    Литература:38
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020