WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

• Семинар по сложности определений, описаний и доказательств, и по алгоритмам (Workshop on computational, descriptive and proof complexity, and algorithms) (г. Москва, НМУ, 29-31 августа 2007 г.) • XXIX Конференции молодых учёных (г. Москва, МГУ, 18 апреля 2007 г.).

Публикации. Основные результаты диссертации опубликованы в четырех работах автора [1–4].

Структура и объем работы. Диссертация состоит из введения и четырех глав. Текст диссертации изложен на 76 страницах. Список литературы включает 36 наименований.

Краткое содержание работы Мы будем нумеровать цитируемые результаты заглавными римскими цифрами, а результаты автора – арабскими цифрами.

Когда мы говорим о булевой функции f, мы обычно подразумеваем, что задана последовательность {fn} булевых функций, где функция fn имеет n n=входных переменных. Мы будем изучать, как ведут себя различные величины, связанные с булевой функцией f, при n стремящемся к бесконечности.

Мы используем следующие стандартные обозначения для асимптотического поведения функций. Пусть f : N N и g : N N. Тогда • f(n) = O(g(n)) означает, что C N n > N |f(n)| C|g(n)|;

• f(n) = (g(n)) означает, что c > 0 N n > N |f(n)| c|g(n)|;

• f(n) = (g(n)) означает, что c, C > 0 N n > N c|g(n)| |f(n)| C|g(n)|;

• f(n) = o(g(n)) означает, что c > 0 N n > N |f(n)| c|g(n)|;

Напомним основное определение работы. Пороговым элементом степени d для булевой функции f : {-1, +1}n {-1, +1} называется всякое выражение вида f(x) = sgn p(x), где p(x) – целочисленный многочлен степени d, а sgn обозначает знаковую функцию: sgn(t) = 1, если t положительно, sgn(t) = 0, если t = 0, и sgn(t) = -иначе. Другими словами, пороговым элементом степени d для f называется целочисленный многочлен, знаковая функция которого совпадает с f. Аналогично, пороговым элементом степени d для булевой функции f : {0, 1}n {0, 1} называется выражение вида 1 + sgn p (x) f(x) =, где p(x) – целочисленный многочлен степени d. То есть, многочлен положителен, когда функция принимает значение 1, и отрицателен иначе.

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

Для всякого b {0, 1} верно b2 = b, а для всякого b {-1, +1} верно b2 = 1. Поэтому пороговый элемент для всякой функции в любом из двух обозначений, всегда можно считать мультилинейным (то есть линейным по каждой переменной).

Особую значимость имеют следующие частные случаи общего понятия порогового элемента. Линейным пороговым элементом называется пороговый элемент степени 1. Обобщенной функцией голосования называется линейный пороговый элемент, у которого все коэффициенты равны ±1.

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

С тремя параметрами порогового элемента связаны три меры сложности булевой функции (в каждой из систем обозначений): минимальная степень порогового элемента для этой функции, называемая пороговой степенью, минимальный вес порогового элемента для этой функции, называемый пороговым весом, и минимальная длина порогового элемента для этой функции, называемая пороговой длиной. Пороговую степень булевой функции f мы будем обозначать через deg(f) (мы скоро докажем, что это определение не зависит от обозначений). Заметим, что поскольку всякую булеву функцию можно реализовать пороговым элементом, и пороговые элементы всегда можно считать мультилинейными, для всякой булевой функции f от n переменных deg(f) n.

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

Будем обозначать через W0,1(f, d) (W±1(f, d)) минимальный вес порогового элемента степени не выше d для функции f в обозначениях {0, 1} (в обозначениях {-1, +1}, соответственно). Будем обозначать через L0,1(f, d) (L±1(f, d)) минимальную длину порогового элемента степени не выше d для функции f в обозначениях {0, 1} (в обозначениях {-1, +1}, соответственно). Эти понятия определены, только в случае d deg(f). Иногда будет не важно, в каких именно обозначениях мы рассматриваем булеву функцию или обозначения будут ясны из контекста. Тогда мы будем писать просто W (f, d) и L(f, d).

Сразу заметим, что если deg(f) d1 d2, то из определения видно, что W (f, d1) W (f, d2) и L(f, d1) L(f, d2). То есть величины W (f, d) и L(f, d) (в обоих обозначениях булевых переменных) не могут увеличиваться при росте d.

Реализация булевых функций пороговыми элементами соответствует реализации булевых функций булевыми схемами специального вида. Более точно, пусть F – некоторое семейство булевых функций. Персептроном в базисе F называется булева схема глубины 2 с линейным пороговым элементом на верхлинейный пороговый элемент · · · f1 f2 fk · · · x3 x1 x7 x3 x6 x8 x7 x8 x· · · нем уровне и с произвольными булевыми функциями f1,..., fk из F на нижнем уровне (смотри рисунок).

Нетрудно заметить, что пороговый элемент для булевой функции в обозначениях {0, 1} соответствует линейной пороговой функции, в которую подставили произведения переменных. Так как произведение булевых переменных в обозначениях {0, 1} соответствует их конъюнкции, мы получаем, что пороговый элемент для булевой функции в обозначениях {0, 1} соответствует персептрону в базисе из конъюнкций. Произведению переменных в обозначениях {-1, +1} соответствует их сумма по модулю два, поэтому пороговый элемент для булевой функции в этих обозначениях соответствует персептрону в базисе из функций логического сложения. Заметим, что длина порогового элемента соответствует размеру персептрона (числу ребер в нем), точнее эти величины отличаются не более чем в n + 1 раз. Если же мы потребуем, чтобы на верхнем уровне персептрона была не линейная пороговая функция, а обобщенная функция голосования, то размеру схемы будет соответствовать вес порогового элемента.

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

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

Реализация булевых функций пороговыми элементами в обозначениях {0, 1} и в обозначениях {-1, +1} – это, вообще говоря, разные реализации. Это видно хотя бы по соответствующим булевым схемам. Однако, между реализациями в разных обозначениях есть связь. Сейчас мы приведем известные результаты на эту тему.

Сначала установим соотношение между переменными в обозначениях {0, 1} и {-1, +1}. Будем обозначать булеву переменную в обозначениях {-1, +1} через b, а ту же булеву переменную в обозначениях {0, 1} через b. Тогда, легко проверить, что b = (1 - b) (напомним, что "истине" соответствует 1 в обозначениях {0, 1} и -1 в обозначениях {-1, +1}). Обратно, b = 1 - 2b.

Предположим теперь, что p(x1,..., xn) – пороговый элемент степени d для функции f в обозначениях {-1, +1}. Тогда ясно, что многочлен p(1-2x,..., 12x) будет пороговым элементом степени d для f в обозначениях {0, 1}. Обn ратно, если p(x,..., x) – пороговый элемент степени d для функции f в обо1 n значениях {0, 1}, то 2dp(1(1 - x1),..., (1 - xn)) – пороговый элемент степени 2 d для функции f в обозначениях {-1, +1} (множитель 2d нужен, чтобы сделать коэффициенты многочлена целыми, так как после замены переменных m они имеют вид, где m – целое, а k d).

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

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

Мы приведем здесь известные результаты о таких соотношениях. Про пороговую длину известно, что она может сильно меняться при смене обозначений.

В работе Гольдмана42 была доказана следующая теорема.

Теорема I (Гольдман). Функция логического сложения от n переменных имеет пороговую длину 1 в обозначениях {-1, +1} и экспоненциальную (от числа переменных) пороговую длину в обозначениях {0, 1}.

Mikael Goldmann. On the power of a threshold gate at the top. Inf. Process. Lett., 63(6):287–293, 1997.

Первое утверждение этой теоремы несложно, так как легко увидеть, что ixi = xi в обозначениях {-1, +1}. Существенной частью этого результата i является нижняя оценка на длину пороговых элементов в обозначениях {0, 1}.

С другой стороны, в работе43 была доказана следующая теорема.

Теорема II (Краузе, Пудлак). Существует (явно заданная) функция полиномиальной пороговой длины в обозначениях {0, 1}, но экспоненциальной пороговой длины в обозначениях {-1, +1}.

Ситуация с весами другая. Теорема I легко переносится на веса пороговых элементов. Действительно, функция логического сложения представима пороговым элементом с весом 1, а с другой стороны, пороговый вес всегда не меньше пороговой длины, так что функция логического сложения имеет экспоненциальный пороговый вес в обозначениях {0, 1}. Однако, в обратную сторону, в работе44 был доказан следующий результат.

Теорема III (Краузе, Пудлак). Bсякая функция от n переменных с пороговым весом W в обозначениях {0, 1} имеет пороговый вес O(n2W ) в обозначениях {-1, +1}.

Так что, если существует пороговый элемент полиномиального веса для некоторой функции в обозначениях {0, 1}, то такой же пороговый элемент существует для этой функции и в обозначениях {-1, +1}. Отметим также, что из доказательства в работе45 следует также такой результат.

Теорема IV (Краузе, Пудлак). Для всякой функции f и всякого d deg(f) верно W±1(f, d) O(n2W0,1(f, d)) Таким образом, соотношение из теоремы III между пороговыми весами заданной функций f в различных обозначениях верно также и для величин W±1(f, d) и W0,1(f, d).

Наконец, пусть булева функция f от n переменных представима пороговым элементом p(x), степень которого постоянна и не зависит от n. Тогда путем Matthias Krause and Pavel Pudlk. Computing Boolean functions by polynomials and threshold circuits.

Comput. Complex., 7(4):346–370, 1998.

Matthias Krause and Pavel Pudlk. Computing Boolean functions by polynomials and threshold circuits.

Comput. Complex., 7(4):346–370, 1998.

Matthias Krause and Pavel Pudlk. Computing Boolean functions by polynomials and threshold circuits.

Comput. Complex., 7(4):346–370, 1998.

раскрытия скобок в заменах переменных, описанных ранее, легко увидеть, что вес порогового элемента увеличивается не более чем в константу раз при таких заменах. То есть, верно следующее утверждение.

Лемма V (Фольклор). Если функция f от n переменных представима пороговым элементом постоянной, не зависящей от n, степени d, то W0,1(f, d) = (W±1(f, d)).

Таким образом, если нас интересует величина W (f, d), где d – постоянно и не зависит от числа переменных n, то не имеет значения в каких обозначениях рассматривается функция (все результаты у нас будут с точностью до постоянного множителя).

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

Во Введении показывается актуальность исследуемых вопросов, содержится краткое изложение истории их изучения и обзор результатов диссертации.

В главе 1 сформулированны основные определения и собраны известные результаты, используемые в доказательстве.

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

Еще в 60-х годах были получены нижние оценки вида 2(n) на веса пороговых элементов степени d = 1 (то есть, линейных пороговых элементов) для конкретных функций (первый такой результат был получен в46). Однако, они не достигали известной верхней оценки nO(n), доказанной в работе Муроги(смотри также48).

Теорема VI (Мурога). Для всякой булевой функции f от n переменных, если deg(f) = 1, то W (f, 1) = nO(n).

Позднее Хостад49 доказал точную (вплоть до константы в экспоненте) нижнюю оценку.

J. Myhill and W. H. Kautz. On the size of weights required for linear-input switching functions. IRE Trans.

on Electronic Computers, 10(2):288–290, 1961.

Saburo Muroga. Threshold logic and its applications. Wiley-Interscience, Chichester, 1971.

Johan Hstad. On the size of weights for threshold gates. SIAM J. Discret. Math., 7(3):484–492, 1994.

Johan Hstad. On the size of weights for threshold gates. SIAM J. Discret. Math., 7(3):484–492, 1994.

Теорема VII (Хостад). Существует (явно заданная) функция f от n переменных такая что deg(f) = 1 и W (f, 1) = n(n).

d Для случая d > 1 из теоремы VI легко получается верхняя оценка nO(n ) на веса пороговых элементов степени d для заданных функций.

Следствие VIII. Для всякой булевой функции f от n переменных, если d deg(f) = d, то W (f, d) = nO(n )(здесь константа в O зависит от d).

Действительно, в пороговом элементе степени d не более O(nd) одночленов.

Заменим их на новые независимые переменные. Тогда мы получим линейный пороговый элемент от O(nd) переменных. Согласно теореме VI, он эквиваd лентен некоторому пороговому элементу с весом nO(dn ). Заменяя в новом линейном пороговом элементе переменные обратно на одночлены, мы получаем требуемую оценку.

В главе 2 мы доказываем, что эта верхняя оценка точна.

Теорема 1. Для всякого d существует (явно заданная) булева функция f d такая что deg(f) = d, и W (f, d) = n(n ) (константа в зависит от d).

Эта теорема не получается из теоремы VII также легко, как следствие VIII из теоремы VI. До этого результата для пороговых элементов степени d > не было известно нижних оценок лучше, чем 2(n).

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»