Конференции ИВТ СО РАН

Тезисы докладов

"P versus NP&co-NP" В КОНТЕКСТЕ ПРОБЛЕМЫ ОБРАЩЕНИЯ ДИСКРЕТНЫХ ПЕРЕСТАНОВОК Семенов А.А. В несимметричной криптографии и теории криптографических протоколов одним из основных объектов являются односторонние функции. На сегодняшний день не известно ни одного явного примера односторонней функции. Более того, построение такого примера означало бы конструктивное доказательство соотношения P<>NP . Автором данной работы в статьях [1], [2] была предложена процедура, позволяющая сводить проблемы обращения одного класса дискретных функций к проблеме, находящейся в NP&co-NP. Оказалось, что в данный класс попадают проблемы обращения большинства известных предположительно односторонних функций, встречающихся в криптографии с открытым ключом. Сказанное означает, что в предположении P=NP&co-NP некоторые используемые на практике несимметричные криптосистемы не являются стойкими. Таким образом, весьма актуальной можно считать задачу аргументации соотношения P<>NP&co-NP. В работе [3] приведен результат P<>NP&co-NP в контексте одного класса ветвящихся программ (т.н. "read-once branching programs"). Такого сорта вычислительные модели являются ограниченными, поэтому интерес к данной проблеме в контексте "классических" вычислительных устройств остается. В предлагаемой работе отправной точкой для аргументации включения является следующий объект. Определение. Конъюнктивная нормальная форма (КНФ) над множеством булевских переменных X называется сильно обусловленной, если она выполнима в точности на одном наборе значений истинности переменных из X. Можно показать, используя т.н. "консервативные сводимости", что к проблеме поиска выполняющего набора сильно обусловленной КНФ можно свести проблему обращения произвольной дискретной перестановки. В этом смысле описанную проблему можно считать полной в классе проблем обращения дискретных перестановок. Класс сильно обусловленных КНФ обладает следующими свойствами. Лемма. Проблема поиска набора, выполняющего произвольную сильно обусловленную КНФ, сводится по Куку к проблеме из NP&co-NP, тогда как проблема распознавания сильно обусловленных КНФ является co-NP-трудной. Опираясь на данную лемму, можно показать справедливость следующего утверждения. Основная теорема. В предположении, что полиномиальная иерархия Стокмейера не стабилизируется на втором уровне, имеет место следующее соотношение P<>NP&co-NP. Одним из следствий данной теоремы является явный пример задачи в NP&co-NP, не попадающей в P в предположении, что полиномиальная иерархия не стабилизируется на втором уровне. Следствие основной теоремы. Следующая проблема находится в (NP&co-NP)P в предположении, что полиномиальная иерархия не стабилизируется на втором уровне. По произвольной КНФ C, относительно которой известно, что она сильно обусловлена над множеством из n булевских переменных, и натуральному числу k из множества {1,...,n} определить, верно ли, что k-тый бит выполняющего C набора равен 1». ЛИТЕРАТУРА [1] Беспалов Д.В., Семенов А.А. О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ. Вычислительные технологии. 2002, Т. 7, Ч. 2, С. 18-25. [2] Семенов А.А. К общему определению односторонних функций. Вестник ТГУ, 2003, приложение № 6, с. 18-24. [3] S. Jukna, A. Razborov, P. Savicky and I. Wegener On P versus NP&co-NP for Decision Trees and Read-Once Branching Programs. Computational Complexity, Vol. 8, No 4, 1999, pages 357-370.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск