Кратчайшая формула для n-членного монотонного CNF

10

Монотонная формула CNF с m членами на n переменных ( ) - это формула вида , где каждый является ИЛИ некоторого подмножества переменных и находятся в диапазоне от до . f ( x 1 , , x n ) = C i C i x 1 , , x n i 1 мИкс1,...,ИксNе(Икс1,...,ИксN)знак равноСяСяИкс1,...,ИксNя1м

Например, - это монотонная формула CNF с 2 членами на 4 переменных.(Икс1Икс3Икс4)(Икс2Икс4)

Я ищу самую короткую формулу (не обязательно монотонную, не обязательно CNF, подойдет любая формула!) Для того же набора переменных, который представляет ту же функцию, что и заданная монотонная формула CNF для n переменных с n членами. (Обратите внимание, что количество терминов и переменных одинаково.)

Одним из очевидных способов построения формулы является расширение данного определения CNF, которое даст нам формулу размера . (Давайте определим размер формулы как длину формулы, когда она записана в виде строки.) Я хочу знать, является ли это наиболее эффективной общей конструкцией или существует ли для каждого n-членного монотонного CNF формула? размером .o ( n 2 )О(N2)о(N2)

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

РЕДАКТИРОВАТЬ: я добавляю пример, чтобы сделать яснее.

Скажем, входная формула имеет вид . Это монотонная формула CNF. Более короткая формула , которая представляет собой ту же самую функцию , состоит в следующем: х 1( х 2х 3... х п ) .езнак равно(Икс1Икс2)(Икс1Икс3)...(Икс1ИксN)Икс1(Икс2Икс3...ИксN)

Робин Котари
источник

Ответы:

11

Вы можете получить нижнюю границей , используя счетную аргумент: есть е х р ( п 2 ) п термы У на п переменных (это легко , но требует немного заботы, чтобы убедиться , что перерасчет не существует), но есть формулы e x p ( s log s ) (или даже схемы) размером не более s . Ω(N2/журналN)еИксп(N2) NNеИксп(sжурналs)s

Кажется , что выигрыш в последний фактор будет трудно , так как это потребовало бы доказать квадратичная нижняя граница по формуле размера, и я думаю, что некоторые существующие методы для этого не хватает. O ( n 2 / log n ) может даже быть правильным ответом - по крайней мере, для размера схемы - с использованием некоторой техники, подобной четырем русским .журналNО(N2/журналN)

Ноам
источник
Отлично, спасибо! Фактор log n на самом деле не так важен для меня, так что это полностью отвечает на мой вопрос.
Робин Котари
2

Учтите, что для любого CNF вы можете вычислить множество простых импликатов (из которых любой минимум должен быть подмножеством), взяв замыкание в соответствии с разрешением и применив исключение из подсчета.

Однако в случае любого монотонного CNF закрытие разрешения F равно F (поскольку отрицательных литералов нет, разрешение невозможно). Следовательно, минимальный CNF - это множество простых импликатов, и это именно та формула, которую вы уже имеете.FFF

Конечно, я предполагаю, что вы не хотите вводить новые переменные.

Если вы хотите убедиться, что у вас есть какая-то формула, которая имеет терминов, то, как вы предлагаете, единственный способ получить это - расширить некоторые пункты, добавив отсутствующие переменные. Любой такой CNF должен иметь одинаковое количество литералов (размер, который, как я полагаю, вы полагаете) для фиксированных f и n .NеN

MGwynne
источник
Прекрасно, мне это нравится. (Попутно, в случае возникновения монотонного дела DNF, @Robin, я думаю, это может быть интересно: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4716 )
Даниэль Апон,
1
Я не уверен, что понимаю. Минимальный размер CNF может быть монотонной формулой CNF, которая у меня уже есть, но я ищу формулу наименьшей длины из всех видов. Это не должно быть CNF или монотонным. Я отредактирую свой вопрос, чтобы сделать это понятнее.
Робин Котари
1
Ах я вижу. Ну, то, что я говорил, охватывает, если это должен быть CNF. Если это может быть произвольная пропозициональная формула, то мне нужно больше думать.
MGwynne