Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография
18.01.2005
    

Вопросы:

  1. В каком состоянии сейчас находится проблема $\mathrm{NP}$-полноты? Возможно ли где-нибудь ознакомиться с результатами последних исследований в данной области (предпочтительны русскоязычные материалы). Уже достаточно давно встречаю в Сети подобные ресурсы: http://www.tarusa.ru/~mit/RUS/rus.php, но, к сожалению, не вижу результата подобных заявлений.
  2. Интересует задача факторизации больших чисел и ее соотношение с классом $\mathrm{NP}$-полных задач. На вышеупомянутом ресурсе по ссылке http://www.tarusa.ru/~mit/RUS/crypt.php можно найти информацию о том, что задача факторизации и $\mathrm{NP}$-полные задачи (приведен пример задачи ВЫПОЛНИМОСТЬ) имеют одинаковый порядок роста сложности по входным данным. На основании этого косвенно можно предположить, что задача факторизации является $\mathrm{NP}$-полной. Кто-нибудь занимается или занимался вопросами доказательства отнесения задачи факторизации к классу $\mathrm{NP}$-полных задач? Хотелось бы услышать на этот счет авторитетное мнение.
  3. Чисто гипотетический вопрос. Что изменится в теоретической и прикладной криптографии в случае доказательства соотношения $\mathrm{P}=\mathrm{NP}$ (т. е. отыскания полиномиального алгоритма для какой-либо $\mathrm{NP}$-полной задачи)?


Ответы:

1. По-видимому вопрос сформулирован не совсем точно и речь идет не о проблеме $\mathrm{NP}$-полноты, а о знаменитой проблеме соотношения классов $\mathrm{P}$ и $\mathrm{NP}$.

Впрочем, в теории сложности вычислений есть область исследований, которую можно было бы назвать проблемой $\mathrm{NP}$-полноты. Здесь следует отметить, что общеизвестный и широко используемый термин "$\mathrm{NP}$-полная задача" с математической точки зрения не вполне корректен. Полнота определяется для пары (класс сложностей, тип сводимости) и математически строгое определение говорит о задаче, полной в данном классе относительно данного типа сводимости. Уже в своих основополагающих работах Кук и Карп использовали разные типы сводимости. Существуют и другие сводимости, в т. ч., например, рандомизированные. Каждый тип сводимости определяет свое множество задач, полных в классе $\mathrm{NP}$. Вопрос о соотношениях между такими множествами (совпадают или различаются) во многих случаях остается открытым и с полным основанием может называться проблемой $\mathrm{NP}$-полноты. Подчеркнем, что эта проблема представляет интерес главным образом в контексте исследования структуры класса $\mathrm{NP}$. Когда же речь идет о сложности какой-либо конкретной задачи $T$, то достаточно продемонстрировать произвольную (полиномиальную, детерминированную) сводимость, скажем, задачи ВЫПОЛНИМОСТЬ к $T$. Это будет свидетельством вычислительной сложности задачи $T$ в том смысле, что из существования для нее полиномиального детерминированного алгоритма будет следовать, что $\mathrm{P}=\mathrm{NP}$.

Теперь о проблеме соотношения классов $\mathrm{P}$ и $\mathrm{NP}$. На данный момент она является одной из наиболее важных и наиболее популярных нерешенных математических проблем. С сожалением приходится констатировать, что проблема эта стала даже слишком популярной. Не будет большим преувеличением сказать, что ферматисты XXI века доказывают, что $\mathrm{P}=\mathrm{NP}$. Работы с такими "доказательствами" публикуются регулярно и, как правило, несут на себе печать "синдрома непризнанного гения": безудержное самовосхваление, претензии на какие-то выдающиеся открытия, позволяющие одним махом решить все мировые проблемы, и, главное, отсутствие корректных определений и доказательств. Гораздо реже "доказательства" утверждения $\mathrm{P}=\mathrm{NP}$ публикуются достаточно квалифицированными математиками, просто допустившими какой-либо просмотр в своих рассуждениях. И уж совсем редко встречаются работы, в которых предпринимаются попытки (также несостоятельные) доказать, что $\mathrm{P}\ne\mathrm{NP}$.

Безусловно, ведутся в связи с этой проблемой и серьезные исследования, но, как уже было сказано выше, проблема соотношения классов $\mathrm{P}$ и $\mathrm{NP}$ остается открытой. Тем не менее, на наш взгляд, состояние исследований этой проблемы и "вокруг нее" заслуживает несколько более подробного обсуждения на нашем сайте.

Прежде всего о литературе. Всем известна монография Гэри и Джонсона [1]. Некоторую дополнительную информацию можно найти в книге [2]. На русском языке никаких изданий с более полным освещением данной проблематики нам не известно. Более того, и англоязычные первоисточники в нашей стране труднодоступны. Основные результаты докладываются на специализированной конференции STRUCTURE (IEEE Structure in Complexity Theory Conference), а также на двух самых престижных международных симпозиумах по математической кибернетике: STOC (ACM Symposium on Theory of Computing) и FOCS (IEEE Symposium on the Foundations of Computer Science). Проблема труднодоступности первоисточников весьма серьезна, так, например, для некоторых из цитируемых ниже работ мы не можем даже указать номера страниц! (Ситуация с литературой по математической криптографии не намного лучше, поскольку наиболее значительные результаты публикуются в основном в трудах все тех же симпозиумов STOC и FOCS).

Все используемые ниже и необъясняемые в тексте понятия можно найти в книгах [1], [2].

Начнем с замечания, что в теории сложности существуют и другие не менее интересные и трудные проблемы. Вопрос о соотношении классов $\mathrm{P}$ и $\mathrm{NP}$ --- это часть общей проблемы соотношения между детерминированными и недетерминированными вычислениями. А имеется еще, например, и любопытная проблема соотношения ограничений на время и ограничений на память. Через $\mathrm{PSPACE}$ ($\mathrm{LOGSPACE}$) обозначается класс языков, распознаваемых детерминированными машинами Тьюринга на полиномиальной (логарифмической) памяти. Следующая цепочка включений почти очевидна.

$\mathrm{LOGSPACE}\subseteq\mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}$.

Но вопрос о том, какие из трех включений в данной цепочке являются строгими, остается открытым. Известно, что класс $\mathrm{PSPACE}$ шире класса $\mathrm{LOGSPACE}$ (так называемая теорема об иерархии). Поэтому хотя бы одно из этих трех включений должно быть строгим. Можно предположить, что все три являются таковыми. Тогда, вроде бы, следует сначала взяться за более "легкую" задачу --- отделить класс $\mathrm{P}$ от $\mathrm{PSPACE}$. Соотношение этих классов --- еще одна из центральных нерешенных проблем теории сложности.

Также заслуживает пристального внимания и проблема соотношения вероятностных и недетерминированных вычислений и соответствующих классов сложностей. Очевидно, что $\mathrm{P}\subseteq\mathrm{BPP}$ ($\mathrm{BPP}$ --- вероятностный аналог класса $\mathrm{P}$). Неспециалисты в теории сложности почему-то убеждены, что $\mathrm{BPP}\subseteq\mathrm{NP}$. На самом деле, ни это включение, ни противоположное ему ($\mathrm{NP}\subseteq\mathrm{BPP}$), на данный момент не доказаны. Статус класса $\mathrm{BPP}$ вообще весьма любопытен. Известно, что $\mathrm{BPP}\subseteq\Sigma^p_2$ (см. [3]). Здесь $\Sigma^p_2$ --- класс второго уровня полиномиальной иерархии. При этом не доказано даже, что класс $\mathrm{NEXP}$ шире чем $\mathrm{BPP}$ (класс $\mathrm{NEXP}$ определяется аналогично классу $\mathrm{NP}$ с заменой ограничений вида $O(n^k)$ на ограничения вида $O(2^{n^k})$). С другой стороны, ведутся исследования по дерандомизации эффективных вероятностных алгоритмов. Сформулирована гипотеза (некоторым специалистам она кажется правдоподобной), при которой $\mathrm{P}=\mathrm{BPP}$ [4].

За прошедшие годы были опубликованы многочисленные работы, посвященные исследованиям релятивизированных классов сложностей, подтвердившим, косвенным образом, трудность указанных проблем. Например, построены оракулы $A$ и $B$ такие, что $\mathrm{P}^A=\mathrm{NP}^A$, но $\mathrm{P}^B\ne\mathrm{NP}^B$ [5]. Этот результат показывает, что проблема соотношения классов $\mathrm{P}$ и $\mathrm{NP}$ не может быть решена никаким методом, допускающим релятивизацию (а таких в математике подавляющее большинство). По-видимому, совсем уж неожиданным, на первый взгляд, должен показаться следующий результат: существует оракул $C$ такой, что $\mathrm{BPP}^C=\mathrm{NEXP}^C$ [6].

Существует следующий вполне очевидный путь для отделения класса $\mathrm{NP}$ от $\mathrm{P}$: взять какую-либо $\mathrm{NP}$-полную задачу и доказать для нее сверхполиномиальную нижнюю оценку сложности. Ввиду известной двойственности между машинами Тьюринга и схемами из функциональных элементов, можно использовать любую из этих моделей вычислений. По ряду причин, которые мы здесь обсуждать не будем, схемы представляются более удобной моделью для исследования проблемы нижних границ сложности. Так вот, насколько нам известно, на данный момент наиболее высокая нижняя оценка схемной сложности для конкретной (индивидуальной) функции имеет порядок $4n$, где $n$ --- длина входа [7]. Подчеркнем, что это --- весьма нетривиальный результат.

Так в чем же причина, почему прогресс за три десятилетия в решении такой интересной и важной проблемы столь незначителен? Разумеется, пока проблема соотношения классов $\mathrm{P}$ и $\mathrm{NP}$ не решена, точного и окончательного ответа на этот вопрос не будет. Можно высказать лишь гипотезу. Обратимся к другим разделам математики и посмотрим, чем они занимаются. Что нам известно, к примеру, о функциях, отображающих отрезок $[0,1]$ в себя? Только то, что почти всякая функция разрывна почти всюду. Математический анализ изучает только те функции, которые обладают достаточной гладкостью. Такие функции составляют лишь ничтожную долю множества всех функций, но обладают хорошими свойствами, позволяющими применять методы, наработанные на данный момент. А что знает математика о произвольном множестве, пусть даже конечном? Тоже практически ничего. В алгебре же изучаются множества, наделенные хорошей, "удобной" структурой: группы, кольца и т. п.

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

Вопреки распространенному мнению математиков, неспециалистов в теории сложности вычислений, положение дел с нижними оценками сложности конкретных задач не отличается принципиально от состояния исследований в других областях математики. Стоит ограничить класс рассматриваемых эффективных алгоритмов, как . . . Нет, ничего не становится очевидным или элементарным, но нетривиальные результаты появляются. Так, А. А. Разборов [8] получил сверхполиномиальную нижнюю оценку сложности для конкретной функции в классе монотонных схем, т. е. схем в базисе И, ИЛИ (такие схемы могут вычислять только монотонные функции). Вскоре этот результат был усилен А. Е. Андреевым [9], доказавшим экспоненциальную оценку. Для схем фиксированной глубины сверхполиномиальные нижние оценки были получены Ферстом и др. [10] и Айтаи [11]. Они также в дальнейшем были усилены до экспоненциальных в работах Яо [12] и Хостада [13]. Подчеркнем, что все эти результаты не потребовали изобретения каких-либо искусственных примеров функций. Например, упомянутые нижние оценки сложности схем фиксированной глубины верны для функции четности.

В заключение, о главном вопросе, какого результата в итоге все же следует ожидать: $\mathrm{P}=\mathrm{NP}$ или $\mathrm{P}\ne\mathrm{NP}$? Конечно, пока проблема не решена, никто не даст однозначного ответа. Но все же задумайтесь, какая из следующих двух ситуаций Вам кажется более правдоподобной:


2. По-видимому, под порядком роста сложности в вопросе понимается оценка сверху.

Еще в 1981 г. Шамир и Шреппель [14] предложили алгоритм, решающий некоторые $\mathrm{NP}$-полные задачи за время $O(2^{n/2})$ на памяти $O(2^{n/4})$, где $n$ --- длина входа. Никаких дальнейших продвижений в данном направлении нам неизвестно.

Что же касается задачи факторизации целых чисел, то уже тривиальный перебор дает ту же оценку $O(2^{n/2})$, что и в цитированном результате [14]. Здесь $n$ --- длина двоичной записи факторизуемого числа. Имеются и более быстрые алгоритмы, например, с оценкой $O(2^{n/3})$. Но в целом, можно сказать, что сложность детерминированных алгоритмов для задачи факторизации остается мало исследованной. Это высказывание, казалось бы, противоречит тому факту, что в многочисленных публикациях по криптографии задаче факторизации уделяется достаточно внимания и приводятся оценки ее сложности вида $2^{c\sqrt{n\log n}}$. Однако, во-первых, все это относится к вероятностным алгоритмам, а во-вторых, большинство оценок остаются недоказанными "правдоподобными гипотезами". Более подробно на алгоритмах факторизации мы не останавливаемся, поскольку заинтересованный читатель может ознакомиться с данной темой по книге О. Н. Василенко [15].

Разумеется, сложность наилучшего из известных алгоритмов для какой-либо задачи, даже если она очень высока, ничего не говорит о ее $\mathrm{NP}$-полноте.

На вопрос о том, является ли задача факторизации $\mathrm{NP}$-полной, можно ответить коротко и чисто формально: безусловно, нет. Напомним, что \mathrm{NP} --- это класс языков, или, иначе, задач распознавания (decision problem). Задача факторизации --- это задача поиска решения (search problem) и она, по определению, не может принадлежать классу $\mathrm{NP}$. Но тем не менее, немного изменив подход, вопрос о $\mathrm{NP}$-полноте можно поставить вполне корректно. Например, вместо задачи поиска сомножителей можно рассматривать задачу распознавания языка $L=\{(N,i,\sigma)\}$, где $(N,i,\sigma)\in L$, если $N$ --- составное целое число и $i$-ый бит его максимального множителя равен $\sigma$. Очевидно, что задача факторизации и задача распознавания языка $L$ полиномиально эквивалентны. Альтернативно, можно рассматривать функциональные классы сложностей, состоящие из задач поиска решения. Например, задача ВЫПОЛНИМОСТЬ ставится так: дана булева формула, требуется найти набор значений переменных, на котором эта формула принимает значение $1$. Функциональные аналоги классов сложностей, как правило, обозначают, добавляя букву F к соответствующему названию: $\mathrm{PF}$, $\mathrm{NPF}$ и т. п. Следует заметить, что соотношение между сложностью задач поиска решения и соответствующих задач распознавания представляет собой нетривиальную проблему. Ее исследование имеет большое значение для теории алгоритмов, теории сложности и математической криптографии. Но это --- тема для отдельного разговора.

К моменту возникновения теории $\mathrm{NP}$-полноты в математике было известно довольно много задач, которые решались тривиальным перебором за экспоненциальное время, и для которых не удалось найти полиномиальные алгоритмы. Для большинства этих задач относительно быстро и несложно была установлена $\mathrm{NP}$-полнота (или $\mathrm{NP}$-трудность). В некоторых случаях доказательство $\mathrm{NP}$-полноты потребовало определенных усилий. Были и такие примеры, когда попытки доказательства $\mathrm{NP}$-полноты не увенчались успехом, и в конце концов было доказано, что задача принадлежит классу $\mathrm{P}$ (как в случае задачи линейного программирования). А несколько задач, как говорится, "повисли". Самые известные из них --- факторизация, дискретное логарифмирование и изоморфизм графов.

Заметим, что если $\mathrm{P}=\mathrm{NP}$, то все языки в классе $\mathrm{NP}$ являются полными. Так что доказать, что какой-либо язык не является $\mathrm{NP}$-полным, не отделив при этом класс $\mathrm{P}$ от $\mathrm{NP}$, невозможно. Но можно доказать условный результат типа: если $\mathrm{P}\ne\mathrm{NP}$, то . . . Всюду ниже, до конца обсуждения, мы предполагаем истинной следующую гипотезу: полиномиальная иерархия не вырождается, т. е. нетривиальна (говорят, что полиномиальная иерархия вырождается, если для всех $i$, кроме конечного числа, $\Sigma_{i+1}^p=\Sigma_i^p$, $\Pi_{i+1}^p=\Pi_i^p$).

Любопытно, что вопрос о вычислительной сложности задач факторизации, дискретного логарифмирования и распознавания изоморфизма графов интересен прежде всего с точки зрения криптографических приложений, и именно математическая криптография дала инструмент, позволивший, частично и условно, решить проблему их $\mathrm{NP}$-полноты. Из теоремы Фортнау [16] и некоторых других результатов следует, что если для какого-либо $\mathrm{NP}$-полного языка существует протокол интерактивного доказательства со статистически нулевым разглашением, то полиномиальная иерархия вырождается. Таким образом, наличие для языка доказательства со статистически нулевым разглашением является косвенным аргументом против его (языка) $\mathrm{NP}$-полноты. Такие доказательства были построены для языков ИЗОМОРФИЗМ ГРАФОВ и КВАДРАТИЧНЫЕ ВЫЧЕТЫ. Следовательно, задача распознавания изоморфизма графов не может быть $\mathrm{NP}$-полной. Задача факторизации полиномиально эквивалентна задаче извлечения квадратных корней по составному модулю. К последней полиномиально сводима задача распознавания квадратичных вычетов. Если бы удалось доказать полиномиальную сводимость и в обратную сторону, то из этого следовало бы, что задача факторизации не может быть $\mathrm{NP}$-полной. Альтернативно, тот же результат можно получить, если удастся построить доказательство со статистически нулевым разглашением для определенного выше языка $L$.

Следует иметь в виду, что для задач из класса $\mathrm{NP}$ нет никакого "закона 0-1". Еще в 1975 г. Ладнер [17] доказал, что если $\mathrm{P}\ne\mathrm{NP}$, то в $\mathrm{NP}\setminus\mathrm{P}$ имеется бесконечно много задач, которые не являются $\mathrm{NP}$-полными.

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


3. Ну, уж этот вопрос никак нельзя назвать чисто гипотетическим. Очень важно иметь четкое представление, что произойдет с криптографией, если вдруг окажется, что $\mathrm{P}=\mathrm{NP}$ или $\mathrm{NP}\subseteq\mathrm{BPP}$. Тем более, что, как нам представляется, произойдет нечто из ряда вон: криптография, и теоретическая и практическая, по существу прекратят свое существование. "Выживут" шифры типа Вернама с одноразовыми ключами, схемы аутентификации типа Симмонса, также с одноразовыми ключами, схемы разделения секрета. И, по большому счету, все.

Криптографы, как правило, "с порога" отвергают этот тезис, не желая слушать никакие доводы. Тех же, кто готов данный тезис обдумывать, мы приглашаем: давайте разбираться.

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

Поскольку мы предполагаем, что $\mathrm{P}=\mathrm{NP}$ или $\mathrm{NP}\subseteq\mathrm{BPP}$, для каждой задачи из $\mathrm{NP}$ имеется полиномиальный алгоритм, не суть важно какой, детерминированный или вероятностный.

Первое возражение против нашего тезиса обычно таково. Теория сложности работает с задачами, у которых длина входа стремится к бесконечности, и дает результаты, верные лишь асимптотически. Но во-первых, если любую вычислительную задачу рассматривать лишь на конечном начальном отрезке, то ее сложность --- константа (о константах в вычислительной сложности см. ниже). А во-вторых, можно ли представить себе естественную вычислительную задачу (не искусственно построенный пример), для которой на коротких входах все очень сложно, а с ростом длины входа задача становится все проще и проще?

Второе возражение: даже если $\mathrm{P}=\mathrm{NP}$, неизвестно еще, какие константы будут в полиномах. В самом деле, для каждой задачи из $\mathrm{NP}$ функция сложности будет иметь вид $O(n^k)$, и не важно даже, каков показатель степени $k$, если эта сложность не меньше $C\cdot n^k$ с астрономической константой $C$.

Здесь очень важно понять (факт, имеющий первостепенное значение для понимания всей криптографии), что этой константы $C$ на самом деле нет. Предположим, мы разработали, скажем, криптосистему, сформулировали задачу, стоящую перед противником, и доказали, что минимальная схема из двухвходовых элементов И и ИЛИ и элементов НЕ, решающая эту задачу, имеет сложность $C\cdot n^k$ с устраивающей нас константой $C$. Остается лишь объяснить противнику, что он должен пользоваться только схемами в этом базисе! В самом деле, специалисты по синтезу схем тут же предложат другой базис, также реализуемый на практике, в котором эта константа будет меньше. А ведь существуют и другие модели вычислений, и поскольку при переходе от одной модели к другой константа $C$ "плывет", любое ее значение, даже астрономическое, создает лишь иллюзию защиты от противника.

С показателем степени $k$ ситуация и сложнее и интереснее. Прежде всего, приведем следующий любопытный факт: для всякого $k>0$ существует функция, вычислимая (на детерминированной машине Тьюринга) за время $O(n^{k+1})$ и не вычислимая за время $O(n^k)$ (теорема об иерархии). Истинность этого утверждения не зависит ни от каких недоказанных предположений, в частности от решения проблемы о соотношении классов $\mathrm{P}$ и $\mathrm{NP}$. Почему бы не попытаться использовать эти доказуемо очень сложные функции в криптографии? Дело в том, что теорема об иерархии доказывается диагональным методом и для всех доставляемых ею функций нет более простого описания, чем определяющий их диагональный процесс. Математики же обычно имеют дело с естественными задачами, имеющими короткие и простые описания, такими как известные $\mathrm{NP}$-полные задачи, задача факторизации, задача дискретного логарифмирования и т. п. Так вот, на данный момент не известно ни одной естественной задачи, для решения которой был бы найден полиномиальный алгоритм высокой степени и эта степень не поддавалась бы снижению. Типичные значения показателя степени $k$ для естественных задач --- $1$, $2$, $3$. Можно предположить, что для естественных задач действует своего рода закон 0-1: сложность задачи либо сверхполиномиальна, либо ограничена сверху полиномом невысокой степени. За последнее время это предположение неоднократно высказывалось в качестве научной гипотезы, пока на неформальном уровне.


Литература

  1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  2. Китаев А. Ю., Шень А. Х., Вялый М. Н. Классические и квантовые вычисления. М.: МЦНМО, 1999.
  3. Lautemann C. $\mathrm{BPP}$ and the polynomial hierarchy. Inf. Process. Letters, 17, N 4, 1983, 215--217.
  4. Shaltiel R., Umans C. Simple extractors for all min-entropies and a new pseudo-random generator. FOCS'42, 2001.
  5. Baker T. P., Gill J., Solovay R. Relativizations of the $\mathrm{P}\mathrel{=?}\mathrm{NP}$ question. SIAM J. Comput., 4, N 4, 1975, 431--442.
  6. Heller H. On relativized exponential and probabilistic complexity classes. Information and Computation, 71, 1986, 231--243.
  7. Zwick U. A $4n$ lower bound on the combinational complexity of certain symmetric Boolean functions over the basis of unate dyadic Boolean functions. SIAM J. Comput., 20, 1991.
  8. Разборов А. А. Нижние оценки монотонной сложности некоторых булевых функций. Доклады АН СССР, 281, N 4, 1985, 798--801.
  9. Андреев А. Е. Об одном методе получения эффективных нижних оценок монотонной сложности. Доклады АН СССР, 282, N 5, 1985, 1033--1037.
  10. Furst M., Saxe J., Sipser M. Parity, circuits and the polynomial time hierarchy. Math. Systems Theory, 17, 1984, 13--27.
  11. Ajtai M. $\Sigma^1_1$-formulae on finite structures. Annals of Pure and Applied Logic, 24, 1983, 1--48.
  12. Yao A. C. Separating the polynomial-time hierarchy by oracles. FOCS'26, 1985, 1--10.
  13. Håstad J. Computational limitations for small depth circuits. MIT Press, 1986.
  14. Schroeppel R., Shamir A. A $T=O(2^{n/3})$, $S=O(2^{n/4})$ algorithm for certain $\mathrm{NP}$-complete problems. SIAM J. Comput., 10, N 3, 1981, 456--464.
  15. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. М.: МЦНМО, 2003.
  16. Fortnow L. The complexity of perfect zero-knowledge. STOC'19, 1987, 204--209.
  17. Ladner R. On the structure of polynomial time reducibility. J. of the ACM, 22, N 1, 1975, 155--171.