Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 14.1.3 Криптографические односторонние функции Вверх: 14.1 Односторонние функции Назад: 14.1.1 Модели вычислений   Содержание   Предметный указатель

14.1.2 Односторонние функции в теории сложности

В работах по теории сложности алгоритмов и вычислений исследуются односторонние функции, в определении которых используется традиционная мера вычислительной сложности -- сложность "в наихудшем случае". Такие функции определяются требованием несуществования полиномиальной детерминированной машины Тьюринга, решающей задачу инвертирования функции для всех входных значений. Нетрудно доказать, что функции, односторонние в смысле этого определения, существуют тогда и только тогда, когда P$ {}\ne{}$NP. Более того, подобную функцию легко построить из любого NP-полного языка.

Пусть $ x$ -- слово из NP-полного языка, а $ w$ -- так называемая "догадка" (witness) для $ x$. Например, для задачи ВЫПОЛНИМОСТЬ $ x$ -- это к. н. ф. булевой функции, а $ w$ -- набор значений аргументов, на котором эта функция обращается в 1. Тогда функция $ f(x,w)=x$ -- односторонняя.

С криптографической точки зрения такие функции интереса не представляют, поскольку определение гарантирует лишь существование бесконечных последовательностей значений, на которых эти функции трудно инвертируются.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 14.1.3 Криптографические односторонние функции Вверх: 14.1 Односторонние функции Назад: 14.1.1 Модели вычислений   Содержание   Предметный указатель


Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ
   
TopList Rambler's Top100