Рассматриваем схемы в стандартном базисе. Пусть схемная сложность функции f не больше A, а схемная сложность функции g не больше B. Докажите, что схемная сложность функции f ⊕ g не больше A + B + 5.

задан 11 Мар '19 1:30

Если под стандартным понимается базис из NOT, AND, OR, то прямая сумма реализуется схемой из 5 элементов: f+g = (f and not(g)) or (not(f) and g), откуда получается требуемая оценка.

(11 Мар '19 1:59) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×26
×2

задан
11 Мар '19 1:30

показан
146 раз

обновлен
11 Мар '19 1:59

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

по почте:

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

по RSS:

Ответы

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

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