Схемы из функциональных элементов

В этом разделе мы приведем некоторые необходимые для дальнейшего сведения о булевых функциях.

Схема из функциональных элементов (булева схема) - это способ вычисления булевых функций: B ⁿ® B ^m. Эта схема может быть представлена в виде ациклического графа с тремя видами вершин. Вершинам с нулевой полустепенью захода (число таких вершин равно n) сопоставляются n входных переменных. Вершинам с нулевой полустепенью исхода (число таких вершин равно m) сопоставляются m выходных значений функции.

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

Совокупность таких функций (типов функциональных элементов), на которых строится схема, образует базис схемы. Вычисление происходит поэтапно.

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

Базисом может быть любая полная система булевых функций (вспомним теорему Поста). Поэтому без ограничения общности можно рассмотреть фиксированный базис.

Пример такого базиса дает следующее утверждение следующее утверждение.

Теорема. Базис из трех функций {È, &, Ø} является полным.

Определение. Схема из функциональных элементов (СФЭ) — это конечный ориентированный граф без ориентированных циклов, в каждую вершину которого входит не более 2 рёбер. При этом каждой вершине при­писывается символ: переменная x_j, если в эту вершину рёбра не входят; отрицание, если в вершину входит одно ребро; конъюнкция или дизъюнкция, если в вершину входит 2 ребра. Некоторым вершинам приписывается *. Элементами схемы называются вершины, помеченные логическими операциями.

Сложностью схемы называется число функциональных элементов.

Схемной сложностью L _B (f) вычисления функции f в базисе B называется минимальный размер схемы, вычисляющей f в данном базисе.

Здесь минимум берется по всем схемам, вычисляющим функцию f(n) в базисе B.

Если базис фиксирован, B то индекс опускаем. Отдавая дань истории функция L(n) выражающая максимальную сложность функций от n переменных, называется функцией Шеннона.

Какие для этой функции существуют оценки?

Этот вопрос для нас важен в связи с тем, что СФЭ можно использовать для подхода к анализу сложности задачи.

Рассмотрим задачу в форму распознавания. Закодируем вход задачи Z булевским вектором из B ⁿ, тогда решение задачи – это некоторое отображение φ_z: B ⁿ® B ¹. Предположим, что это отображение в явном виде построено, тогда будет определена некоторая булевская функция. Схемная сложность этой функции может задавать сложность решения задачи.

Опр. Класс булевых функций, для которых существуют схемы полиномиальной сложность и обозначим через P/poly.

В связи с тем, что этот класс будет рассматриваться ниже, нас интересуют оценки функции Шеннона.

Эта задача была решена советским математиком О.Б.Лупановым. Кратко приведем основные результаты.

Утв. L(n) ≤(n +1) 2ⁿ.

Теорема. Справедливо соотношение L(n) < 2ⁿ / n.

Дата добавления: 2015-07-11