Пусть B будет набором логических формул для переменных X = { x 1 , ..., x n } и f : [ n ] → B . При заданной оценке v : X → {0,1} обычным образом до B найдите подмножество S из [ n ] такой, что v ( f ( i )) = 1 для всех i ∈ S (т. Е. Подмножество [ n ], которое отображается в формулы, удовлетворяемые данной оценкой). Наивное решение состоит из тестирования v ( f ( i )) для каждого i ∈ [ n ] и занимает O ( нм ) время в худшем случае, где m - это размер самой большой формулы в изображении f, Мой вопрос: можем ли мы добиться большего успеха, особенно когда n велико, а m мало?
У меня нет предварительной приверженности структурам данных, но для конкретности f может быть представлен в виде массива или словаря и формул с помощью деревьев абстрактного синтаксиса или вложенных списков литералов (предположим, что преобразование в DNF или CNF не проблематично). Кроме того, f изменяется нечасто, в то время как поиски происходят часто. Кажется, что эта проблема сводится к чему-то вроде минимизации булевых цепей, но я не нашел в сети ни одного исследования, которое привело бы к улучшениям по сравнению с простым алгоритмом, упомянутым выше (с разумным временем предварительной обработки).