Другие журналы
Сетевое издание Машины и установки: проектирование, разработка и эксплуатация

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл. № ФС 77-61859. ISSN 2412-592X

Публикации с ключевым словом - NP-полнота

Найдено: 1
77-30569/312834 NP-трудность задачи о восстановлении предыдущего состояния обобщенного клеточного автомата
# 01, январь 2012
доцент, к.т.н. Ключарёв П. Г.
 В статье доказывается NP-трудность задачи о восстановлении  предыдущего состояния обобщенного клеточного автомата, состоящей в следующем: по данному обобщенному клеточному автомату и его заполнению после первого шага найти начальное заполнение. Доказывается также наличие полиномиального алгоритма решения этой задачи для случая обобщенного клеточного автомата, локальная функция связи которого является двухместной. Полученные в статье результаты имеют как теоретическую значимость, так и могут быть применены для обоснования криптографической стойкости алгоритмов шифрования, основанных на обобщенных клеточных автоматах.
 
ПОИСК
 
elibrary crossref neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2017 «Машины и установки: проектирование, разработка и эксплуатация» Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)