Здравствуйте.

Изучаю доказательство теоремы Фишера на нижние оценки NOT гейтов для схем (по книге Stasys Jukna "Boolean Function Complexity" 2011, пункт 10.4,стр 300, ссылка на pdf). В доказательстве говориться, что все пороговые функции $%Th_k(x)$% и $%Th_k(x-x_i)$% можно вычислить схемой размера не более чем $%n^2log^2(n)$%. Однако как это сделать, не говориться.

Вопрос - как это доказать?

С уважением...

задан 27 Ноя '11 5:00

изменен 27 Май '13 15:07

Angry%20Bird's gravatar image


9125

Сформулируйте, какое именно утверждение надо доказать, либо дайте ссылку на книгу.

(27 Ноя '11 5:15) Ignat
10|600 символов нужно символов осталось
3

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

ссылка

отвечен 28 Ноя '11 0:16

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1

задан
27 Ноя '11 5:00

показан
934 раза

обновлен
29 Ноя '11 13:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru