Выражая факт в булевом выражении полиномиального размера

Question

Если у меня есть логические переменные a_1, a_2, .., a_n.Как я могу выразить тот факт, что число булевых переменных, которые установлены в true, больше, чем некоторые k, используя булево выражение полиномиального размера?(Экспонента проста - просто напишите выражения ньютона (n, k)).

Answer 1

Сортируйте логические значения с помощью любой сортировочной сети.Затем просто возьмите (k + 1) -й отсортированный бит, который даст вам результат.

Поскольку каждый из элементов сети сортировки представляет собой пару логических операций, вы можете интерпретировать эту сеть как логическое выражение.С хорошей сетью сортировки это даст вам выражение с O (N * log ² (N)) операциями.

Answer 2

пусть t [i] [j] означает, что из элементов a_1, .., a_i, j из них установлено значение true. Теперь мы можем ясно видеть, что

    t[i][j] => (t[i-1][j] or (t[i-1][j-1] and a_i). 

(поскольку либо переменная уже была установлена ​​в a_1, .., a_ (i-1), либо задана a_i, и в a_1, .., a_ (i-1) есть переменные j-1. Это выражение размера полинома (около n * k переменных t [i] [j], для каждого выражения, подобного тому, которое я написал выше). Тогда, если t [n] [k] истинно, мы получаем, что наша из n переменных по крайней мере k истинна.

Обращаясь к Евгению, отвечу, Чтобы получить переменные в отсортированном порядке (сначала истины, затем ложные значения), мы рассмотрим последовательность t [n] [1], t [n] [2], .. t [n] [n].