Характеристика булевой функции

[Euler-Maskerony]

Здравствуйте. Я хочу решить задачу нахождения функционала, который для данной булевой функции выдает 1 бит. На данном этапе не столь важно какой это именно будет функционал, но он обязательно должен зависеть от всей функции целиком, а также легко вычисляться. Объясняю: любую булевую функцию $N$ переменных можно представить в виде последовательности $2^N$ бит. Данный функционал должен зависеть от всей этой последовательности. Проблема в том, что вся последовательность при больших $N$ нам недоступна, поэтому необходимо найти способ составления такого функционала, который использует функцию так, как она задана, например, с помощью графа вычислений.

Первым (и самым очевидным) решением стала сумма всех выходов функции (по модулю 2). В моем случае, функция задается графом вычислений, узлами которого являются операторы AND, OR, NOT, XOR. Мною была выдвинута гипотеза, что, для выбранного узла, для входов которого данный функционал уже посчитан, можно также его посчитать. Основанием для этого послужило наблюдение, что, если данный узел соответствует оператору XOR, то результатом было бы применение этой операции к значениям функционала обоих входов. Но, к сожалению, у меня так и не получилось приблизиться к решению данной задачи для узла AND, который необходим для полной системы, и я полагаю, что это невозоможно. Также интересным наблюдением стало то, что значение данного функционала для узла равно 1 тогда и только тогда когда в полиноме Жегалкина, соответствующего данному узлу, коэффициент при последнем члене равен 1. Но применения я этому не нашел, т.к. в общем случае полином растет экспоненциально, что не позволяет эффективно использовать данный факт. ДНФ также построить не удастся, по этой же причине.

Самой успешной моей попыткой является следующее:
1) Выбираем первый бит из последовательности, соответствующей данной функции, соединяем его как-то с номером итерации алгоритма (то есть с 1) и хешируем это какой-нибудь хорошей хеш-функцией.
2) Полученный результат является индексом следующего бита, который мы также соединяем с номером итерации (то есть 2) и снова хешируем.
Повторяем это достаточное количество раз.
Таким образом получается функционал, который зависит от какой-то части выходов и эти выходы размазаны по всей последовательности (но он возращает не 1 бит в данном случае, однако всегда можно взять остаток от деления на 2).
Проблема в том, что данный функционал, как я сказал, зависит от какой-то части выходов, потенциально, очень маленькой в случае большого $N$.

Я бы хотел спросить у вас, знаете ли вы что-нибудь по данной теме? Знаете ли вы о подобных функционалах?

P.S. Термин "функционал" я здесь сам ввел и можете к нему не привязываться, просто использовал в значении "функция от функции".

[Евгений Машеров]

На фига, спрашивает поэт Андрей Вознесенский (рифму скромно опускаю). Какова цель построения такой функции? И есть ли ограничения для вида функции (боюсь, что для функции общего вида, задаваемой таблицей, ничего проще $2^n$ не получится)

[mihaild]

Я правильно понимаю, что задача - придумать полиномиально вычислимый функционал, аргументом которого является булева схема, причем:
-для схем, задающих одну и ту же функцию, значения функционала совпадает
-для любого набора, существуют две функции, отличающиеся только на этом наборе, такие что значения функционала на этих функциях отличаются
?

Если да, то интуитивно кажется безнадежным.

[Euler-Maskerony]

mihaild в сообщении #1603226 писал(а):

-для схем, задающих одну и ту же функцию, значения функционала совпадает

Да

mihaild в сообщении #1603226 писал(а):

-для любого набора, существуют две функции, отличающиеся только на этом наборе, такие что значения функционала на этих функциях отличаются

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

Евгений Машеров в сообщении #1603217 писал(а):

На фига, спрашивает поэт Андрей Вознесенский (рифму скромно опускаю). Какова цель построения такой функции? И есть ли ограничения для вида функции (боюсь, что для функции общего вида, задаваемой таблицей, ничего проще $2^n$ не получится)

Ну как же. Тогда можно будет uuid для любой функции строить. Для этого нужно просто будет немного дополнить алгоритм, о котором я спрашиваю.

-- 30.07.2023, 12:17 --

mihaild в сообщении #1603226 писал(а):

Если да, то интуитивно кажется безнадежным.

Евгений Машеров в сообщении #1603217 писал(а):

(боюсь, что для функции общего вида, задаваемой таблицей, ничего проще $2^n$ не получится)

Мне почему-то товарищ мой также говорит, но я всё же склоняюсь думать, что можно найти такой функционал, который можно легко вычислить, и который будет включать все входы. Вы же видите пример с суммой всех выходов. Тут бы немного ещё математика была бы другой, и всё бы уже получилось.
Кстати, функция задается не таблицей, а графом вычислений (или же формулой, но из неё граф легко построить), а таблица нужна, чтобы обобщить определение функции, проще с ней работать и устанавливать отношение эквивалентности.

[mihaild]

Euler-Maskerony в сообщении #1603229 писал(а):

Спорно, но вы посудите сами, что функционал выдает 1 бит, поэтому на любом наборе они не могут различаться

Порядок кванторов такой: $\forall \vec x \exists f, g: (f(\vec x) \neq g(\vec x)) \wedge (\forall y \neq x: f(x) = f(y)) \wedge F(f) \neq F(g)$. Просто иначе я не понимаю, что такое "зависит от всей последовательности [значений]".

Euler-Maskerony в сообщении #1603229 писал(а):

Кстати, функция задается не таблицей, а графом вычислений (или же формулой, но из неё граф легко построить)

Это кстати разные вещи, и теоретически может оказаться важным (бывает что минимальная формула сильно больше чем схема).

[Euler-Maskerony]

mihaild в сообщении #1603232 писал(а):

Просто иначе я не понимаю, что такое "зависит от всей последовательности [значений]".

Я, честно, не знаю как дать формальное определение, но могу попробовать. Это значит, что мы, имея полный доступ к реализации функционала, не можем сказать наверняка, будет ли данный функционал отличаться на двух данных последовательностях или нет, не посчитав его на них (это не формально). То есть, потенциально, для двух последовательностей, отличающихся в одном бите, функционалы могут давать один и тот же результат, но мы этого не узнаем, пока действительно не посчитаем. Контрпример: функционал считающий сумму первых $n$ бит последовательности. Мы точно знаем, что он не зависит, например, от последнего её бита. Также контрпримером можно предложить пример из моего главного сообщения. Тот функционал учитывает какую-то часть бит последовательности так, что посчитав функционал для первой функции (из двух, отличающихся одним выходом), мы часто уверенно сможем сказать, равен ли он его значению для второй функции (зная номер выхода, на котором функции различны, мы проверяем, учитывается ли он в первом функционале).

mihaild в сообщении #1603232 писал(а):

Это кстати разные вещи, и теоретически может оказаться важным (бывает что минимальная формула сильно больше чем схема).

Возможно. В данном случае рассматриваем функции, которые можно задать относительно короткой формулой.

[mihaild]

Euler-Maskerony в сообщении #1603239 писал(а):

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

Я не предлагаю говорить, что изменение любого бита всегда меняет значение функционала (это равносильно тому, что функционал равен либо сумме значений функции, либо сумме $\oplus 1$).

Euler-Maskerony в сообщении #1603239 писал(а):

Контрпример: функционал считающий сумму первых $n$ бит последовательности

Это контрпример к моему предложению (этот функционал Вас устраивает, хотя и не подходит под мое предложение), или просто пример не устраивающего Вас функционала?
Если второе, то можете ли привести пример функционала, который подходит под мое предложение, но Вас не устраивает, либо наоборот?

[Euler-Maskerony]

mihaild в сообщении #1603246 писал(а):

, или просто пример не устраивающего Вас функционала?

Это.

mihaild в сообщении #1603246 писал(а):

Если второе, то можете ли привести пример функционала, который подходит под мое предложение, но Вас не устраивает, либо наоборот?

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

[mihaild]

Euler-Maskerony в сообщении #1603249 писал(а):

Не понимаю почему вы говорите, что оно противоречит моему примеру

Я, видимо, что-то неправильно понял. Фиксируем тогда пока что такое определение.

Я сильно подозреваю, что по нему ничего хорошего сказать нельзя - я не помню результатов, что по булевой формуле можно анализировать функцию лучше, чем просто посчитать значения.

[Geen]

mihaild в сообщении #1603232 писал(а):

Порядок кванторов такой: $\forall \vec x \exists f, g: (f(\vec x) \neq g(\vec x)) \wedge (\forall y \neq x: f(x) = f(y)) \wedge F(f) \neq F(g)$.

У Вас опечатка, похоже

[mihaild]

Geen в сообщении #1603304 писал(а):

У Вас опечатка, похоже

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

[Geen]

mihaild в сообщении #1603326 писал(а):

Вроде кроме потерянной стрелки всё правильно

В середине вместо $f(x)$ должно быть $g(y)$...?

-- 30.07.2023, 22:53 --

А вообще, $N$ фиксировано?

[mihaild]

Geen в сообщении #1603328 писал(а):

В середине вместо $f(x)$ должно быть $g(y)$...?

Да, правда.

[Euler-Maskerony]

Geen в сообщении #1603328 писал(а):

А вообще, $N$ фиксировано?

Не до конца понимаю что это значит, но, наверное, да.

[mihaild]

Если $N$ фиксированно, то у нас конечное число наборов, и можно просто явно выписать таблицу значений:)

Вообще для начала можно взять более простой вариант. Существует ли разбиение булевых функций на два класса, такое что класс функции вычислим за полиномиальное время по формуле, при этом класс функции нельзя определить за полиномиальное время если функция задана оракулом?
(я сильно подозреваю, что это открытый вопрос, и останется таким довольно долго; хотя может быть в такой постановке и есть какой-то хитрый трюк)