Выражение факта в логическом выражении полиномиального размера

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


algorithm boolean-logic reduction complexity-theory boolean-expression
person siemanko    schedule 22.02.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

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

person Evgeny Kluev    schedule 22.02.2012
comment
Вот и все! Я просто не указал, что мне нужно это выражение в CNF (все еще полиномиальное). Можете ли вы придумать пример сортировочной сети, которая позволит мне сделать это достаточно просто? - person siemanko; 22.02.2012
comment
CNF значительно усложняет эту задачу. Я не знаю ни одной сортировочной сети, которая дает выражение CNF. И, насколько я знаю, преобразование любого выражения в CNF может привести к экспоненциальному взрыву выражения в худшем случае. Я не знаю ни одного решения, которое было бы одновременно CNF и полиномиальным. Скорее всего это невозможно. - person Evgeny Kluev; 22.02.2012
comment
Ну, это просто неправда. Большинство экспериментов, которые придумывает человек, вручную можно преобразовать в CNF, также каждая машина Тьюринга может быть записана как выражение CNF с полиномиальной сложностью, поэтому, если мы возьмем машину, которая выполняет сортировку, у нас будет преобразование в полиномиальную сложность. Все, о чем я прошу, — это сеть сортировки, для которой легко записать ее вручную, чтобы доказательство было простым. - person siemanko; 22.02.2012
comment
Каждая известная сеть сортировки производит выражения одной и той же формы: чередование И и ИЛИ. Таким образом, выражение из любой сети будет одинаково просто (или одинаково невозможно) преобразовать в CNF. Я не могу рекомендовать какой-то конкретный. Если вы выбираете простую сеть с небольшим количеством операций, попробуйте Групповую нечетно-четную сортировку слиянием или сортировщик Bitonic. Я все еще думаю о доказательстве того, почему КНФ не может быть полиномиальной. - person Evgeny Kluev; 22.02.2012
comment
Хорошо, но тот факт, что большинство известных вам сетей сортировки могут быть выражены как сат-выражения, которые имеют только каноническое представление экспоненциального размера, не доказывает, что все сети сортировки будут иметь нормальную форму экспоненциального размера, не так ли? Кроме того, я на самом деле нашел полиномиальное выражение 3-CNF, которое эквивалентно клике (что было моей первоначальной проблемой), я не уверен, что такое точное определение сети сортировки, но я совершенно уверен, что подмножество моего выражения может быть использовано для записи сеть сортировки 3-CNF полиномиального размера. - person siemanko; 23.02.2012
comment
Я не настаиваю на том, чтобы все сети сортировки имели нормальную форму экспоненциального размера. Собственно, мое вчерашнее доказательство выглядит неубедительно. Но я все еще не уверен, возможна ли полиномиальная КНФ для вашего случая. И если это возможно, я не знаю, что проще: преобразовать выражение какой-либо сети сортировки в CNF или просто упростить решение из OP. Выражение из вашего сегодняшнего поста не выглядит ни 3-КНФ, ни просто КНФ. - person Evgeny Kluev; 23.02.2012

arrow_upward
0
arrow_downward

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

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

person siemanko    schedule 23.02.2012