Какие монотонные булевы функции представляются в виде пороговых сумм?

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

На самом деле, вы очень внимательно относитесь к этому, и вы предвидели все возможные результаты $2^n$ , и решили для каждого из них, должен ли кандидат с таким показом пройти или не сдать. Таким образом, у вас есть булева функция $f : \{0, 1\}^n \to \{0, 1\}$ которая указывает, должен ли кандидат пройти или потерпеть неудачу в зависимости от его точных ответов. Конечно, эта функция должна быть монотонной : если правильный набор вопросов заставляет вас пройти, то и любой правильный набор супернабора также должен вас пропускать.

Можете ли вы принять решение о баллах (положительных действительных числах) для вопросов и о пороге, чтобы ваша функция $f$ точно отражалась правилом «кандидат проходит, если сумма баллов за правильные вопросы превышает порог» ? (Конечно, порог можно принять равным 1 без потери общности, вплоть до умножения баллов на константу.)

Формально: существует ли характеристика монотонных булевых функций $f: \{0, 1\}^n \to \{0, 1\}$ для которых существуют такие $w_1, \ldots, w_n \in \mathbb{R}_+$ , что для всех , мы имеем тогда и только тогда, когда ? е ( v ) = 1 Е я ш я v I ≥ $v \in \{0, 1\}^n$$f(v) = 1$$\sum_i w_i v_i \geq 1$

Нетрудно понять, что не все функции могут быть представлены таким образом. Например, функция не может: поскольку принято, мы должны иметь , поэтому один из должен быть , а также для . Теперь, если это, например, и , у нас есть противоречие, потому что но отклонено; другие случаи аналогичны.$(x_1 \wedge x_2) \vee (x_3 \wedge x_4)$$(1, 1, 0, 0)$$w_1 + w_2 \geq 1$$w_1, w_2$$\geq 1/2$$w_3, w_4$$w_1$$w_3$$w_1 + w_3 \geq 1$$(1, 0, 1, 0)$

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

Конечно, можно думать о многих вариациях на эту тему. Например, на реальных экзаменах вопросы не являются независимыми, но существует DAG по вопросам, указывающим на зависимость, и кандидаты могут ответить на вопрос, только если были выполнены все предварительные условия. Условие для монотонных функций затем может быть ограничено значениями в которые удовлетворяют зависимостям, и вопрос заключается в том, чтобы определить, можно ли таким образом захватить входную функцию, учитывая входную группу DAG для переменных. Можно также подумать о вариантах, где оценки являются k- кортежами для фиксированного k (суммируются по точкам и сравниваются по точкам с пороговым вектором), которые могут захватывать больше функций, чем $\{0, 1\}^n$$k$$k$ . В качестве альтернативы вы можете использовать более выразительные функции, которые не являются булевыми, а идут в полностью упорядоченном домене с различными пороговыми значениями, которые должны указывать вашу позицию в домене. Наконец, я не уверен, что произойдет, если вы допустите отрицательные оценки (так что вы можете отменить монотонное ограничение для функций).$k = 1$

(Примечание: что заставило меня задуматься об этом, так это раунд выбора Google Code Jam, где кандидаты отбираются, если они достигают определенного порогового значения, и оценки проблем, по-видимому, тщательно продуманы, чтобы отразить, какие наборы проблем считаются достаточными для отбора. Code Jam имеет структуру зависимости от вопросов, с некоторыми вопросами "большого ввода", которые не могут быть решены, если вы сначала не решили вопрос "small input".)

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

Что касается других характеристик, я нашел следующее интересным. Предположим, что у нас есть положительная пороговая функция с уменьшением веса : f ( v 1 , … , v n ) = $w_1\ge w_2\ge\dots w_n$ Тогдав частностимножество входов(V1,...,vп)для которыхF( → v )=1представляет собой порядковый идеал двоичного мажорации решетки с2пточек, который является учился в

Дональд Кнут, «Искусство компьютерного программирования», упражнение 109 раздела 7.1.1.

Говоря неформально, - это тип функции, где создание более ранних битов 1 делает f более вероятным равным 1: так, например, f ( 0 , 1 , 1 ) ≤ f ( 1 , 0 , 1 ) ≤ f ( 1 , 1 , 0 ) . То есть «некоторые биты имеют значение больше», и для устранения избыточных изоморфных случаев мы предполагаем, что более ранние биты имеют значение больше.$f$$f$$f(0,1,1)\le f(1,0,1)\le f(1,1,0)$

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

Действительно, число положительных пороговых функций (с уменьшающимися весами) по переменным задается последовательностью 2 , 3 , 5 , 10 , 27 , 119 , 1113 , … (oeis.org sequence A000617 ), тогда как число таких идеалов порядка равно 2 , 3 , 5 , 10 , 27 , 119 , 1173 , … (oeis.org sequence A132183 )$n$