Какова сложность вычисления дизъюнкции $$\bigvee_{i = 1, ...,n} x_{i}$$ в модели разрешающих деревьев?

задан 6 Фев '18 21:21

@Oldfield: а какова циркумполярная элоквенция бозона Хиггса в переменном магнитном поле эквипотенциального соленоида для уравнения Кадомцева - Петвиашвили второго рода? :)

Это я к той простой мысли, что любые понятия, не относящиеся к обязательной части математических курсов, следует сопровождать пояснениями или ссылками. Иными словами, понятие дизъюнкции знают все, а вот про "модель разрешающих деревьев" слышали только "избранные" :)

(6 Фев '18 21:48) falcao

@falcao Разрешающие деревья для булевых функций. В этой модели требуется вычислить булеву функцию f : {0, 1}^n → {0, 1}, то есть на вход подается ~x = (x1, . . . , xn) ∈ {0, 1}^n и при этом за один ход разрешается спрашивать значение одной переменной из x1, . . . , xn. Формально в рамках нашей общей модели это означает, что в промежуточных вершинах разрешающего дерева могут быть написаны только подмножества множества {0, 1}^n, состоящие из всех векторов, в которых одна фиксированная координата одинакова.

(6 Фев '18 21:56) Oldfield

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

(6 Фев '18 21:57) Oldfield

@Oldfield: если подходить без лишних формальностей, то не будет ли тогда ответом число n? Ясно, что n вопросов заведомо хватает, а меньшего числа уже нет, так как если мы не все переменные знаем, и там везде 0, то значение дизъюнкции нам не известно. Это всё слишком просто выглядит; может ли такое упражнение быть предложено?

(6 Фев '18 23:00) falcao

@falcao Да, слишком просто, что и вызывает сомнения, но меньше n точно нельзя, а больше смысла нет

(7 Фев '18 11:29) Oldfield

@Oldfield: у меня сейчас практически не осталось сомнений в том, что здесь имелось в виду именно это простое решение. Я смотрел в Сети ту лекцию, в которой встречался термин "модель разрешающих деревьев" -- там рассматривались именно такие простенькие примеры, когда шёл разговор о функциях и сложности их вычисления.

(7 Фев '18 18:28) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×827
×59

задан
6 Фев '18 21:21

показан
483 раза

обновлен
7 Фев '18 18:28

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

по почте:

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

по RSS:

Ответы

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

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