Минимизация булевых функций для сжатия данных

[0101]

Булеву функцию проще всего представить в виде ряда нулей и единиц. Чтобы минимизировать, нужно еще предварительно добавить список значений аргументов по крайней мере для единичных значений. Результат минимизации случайной булевой функции скорее всего займет намного больше места, чем исходный бинарный ряд. Есть ли способ представления формулы минимизированной случайной булевой функции, чтобы для ее хранения требовалось меньше места по сравнению с простейшим представлением?

[Sender]

0101 в сообщении #1213103 писал(а):

Есть ли способ представления формулы минимизированной случайной булевой функции, чтобы для ее хранения требовалось меньше места по сравнению с простейшим представлением?

Если речь именно о случайной булевой функции, то, очевидно, нет. Сжать можно только функцию, о которой известно, что её колмогоровская сложность в достаточной мере меньше размера её таблицы истинности.

[0101]

Как оценить колмогоровскую сложность в этом случае?

[Sender]

Ну, учитывая её невычислимость, сделать это будет довольно затруднительно. Способ "в лоб" - перебирать все машины Тьюринга по аналогии с https://en.wikipedia.org/wiki/Busy_beaver в порядке возрастания сложности и взять первую, которая, во-первых, остановится (вот тут основная сложность), а во-вторых, выдаст искомую двоичную последовательность.
Можно ограничиться вычислительными моделями вроде булевых схем или формул, чтобы не иметь дело с проблемой останова, что, вообще говоря, несколько ухудшит компрессию.

[mihaild]

0101 в сообщении #1213125 писал(а):

Как оценить колмогоровскую сложность в этом случае?

Никак. Вы ни про какую функцию не сможете доказать, что ее сложность больше некоторой константы
Зато у случайной функции от $n$ аргументов с вероятностью $0.99$ сложность будет хотя бы $0.99 \cdot 2^{2^n - 1}$.