Проблема принятия решения о том, подразумевает ли монотонный КНФ монотонный ДНФ

14

Рассмотрим следующую проблему решения

Входные данные : монотонный CNF Φ и монотонный DNF Ψ .

Вопрос : ΦΨ тавтология?

Определенно вы можете решить эту проблему в O(2npoly(l)) -time, где n - количество переменных в ΦΨ а l - длина ввода. С другой стороны, эта проблема является coNP-полной. Кроме того, сокращение , которое устанавливает CONP-полноту также показывает , что, если СЕТ не выходит из строя, нет никакого O(2(1/2ε)npoly(l))алгоритм для этой задачи (это верно для любого положительного ε ). Вот это сокращение. Пусть A - (немонотонный) CNF, и пусть x - его переменная. Замените каждое положительное вхождение x на y а каждое отрицательное вхождение x на Z . Сделайте то же самое для каждой переменной. Пусть получающийся монотонный CNF будет Φ . Легко видеть, что A выполнимо тогда и только тогда, когда ΦYZ... не тавтология. Это сокращение увеличивает число переменных в 2 раза, что подразумевает 2N/2 (На основе SETH) нижняя граница, упомянутая выше.

Таким образом, есть промежуток между 2N/2 и 2N временем. Мой вопрос: известен ли какой-нибудь лучший алгоритм или лучшее сокращение от SETH?

Всего два замечания, казалось бы, связанных с проблемой:

  • обратная проблема того, подразумевает ли монотонный DNF монотонный CNF, тривиально разрешима за полиномиальное время.

  • Интересно, что проблема принятия решения о Φ и Ψ вычислить ту же функцию , может быть решена в квазиполинома времени из - за Fredman и Хачиян (О сложности дуализация монотонных дизъюнктивных нормальных форм, журнал алгоритмов 21 (1996), вып. 3 , стр. 618–628, дои: 10.1006 / яг.1996.0062 )

Саша Козачинский
источник

Ответы:

6

Предполагая , что СЕТ, проблема не решаемая во время для любого х > 0 .О(2(1-ε)NпоLY(L))ε>0


Во-первых, позвольте мне показать, что это верно для более общей проблемы, где и Ψ могут быть произвольными монотонными формулами. В этом случае происходит многократное сокращение ctt от TAUT до задачи, которая сохраняет количество переменных. Пусть T n t ( x 0 , , x n - 1 ) обозначает пороговую функцию T n t ( x 0 , , x n - 1 ) = 1ΦΨTTN(Икс0,...,ИксN-1) Используя сортировочную сеть Айтаи-Комлоса-Семереди,T n t можно записать с помощью монотонной формулы полиномиального размера, построенной за времяpoly(n).

TTN(Икс0,...,ИксN-1)знак равно1|{я<N:Иксязнак равно1}|T,
TTNпоLY(N)

Учитывая булеву формулу , мы можем использовать правила Де Моргана, чтобы записать ее в виде ϕ ( x 0 , , x n - 1 , ¬ x 0 , , ¬ x n - 1 ) , где ϕ монотонно. Тогда ϕ ( x 0 , , x n -φ(Икс0,...,ИксN-1)

φ'(Икс0,...,ИксN-1,¬Икс0,...,¬ИксN-1),
φ'является тавтологией тогда и только тогда, когда монотонные значения T n t ( x 0 ,, x n - 1 ) ϕ ( x 0 ,, x n - 1 , N 0 ,, N n - 1 ) действительны для каждогоtn, где N i = T n - 1 t (φ(Икс0,...,ИксN-1)
TTN(Икс0,...,ИксN-1)φ'(Икс0,...,ИксN-1,N0,...,NN-1)
TN
Ni=Ttn1(x0,,xi1,xi+1,,xn1).

Для импликации слева направо пусть будет присваиванием, удовлетворяющим T n t , т. Е. По крайней мере с t . Существует e e с ровно t единицами. потомeTtnteet , следовательно, e ϕ влечет e ϕ ( x 0 , , x n - 1 , N 0 , eNi¬xieϕ . Поскольку это монотонная формула, мы также имеем e ϕ ( x 0 , , x n - 1 , N 0 , , N n - 1 ) . Слева направо аналогично.eϕ(x0,,xn1,N0,,Nn1)eϕ(x0,,xn1,N0,,Nn1)


Теперь позвольте мне вернуться к исходной проблеме. Я покажу следующее: если задача разрешима во времени , то для любого k , k -DNF-TAUT (или дважды k -SAT) разрешима за время 2 δ n + O ( 2δnpoly(l)kkk. Это подразумеваетδ1,если выполняется SETH.2δn+O(knlogn)poly(l)δ1

Итак, предположим, что нам дано -DNF ϕ = i < l ( j A i x jj B i ¬ x j ) ,k

ϕ=i<l(jAixjjBi¬xj),
где для каждого i . Разобьем n переменных на блоки n = n / b размером b |Aя|+|Вя|КяNN'знак равноN/б каждый. По той же причинекак указано выше,φявляется тавтологией тогда и только тогдакогда последствия у < п ' Т Ь т ¯u ( х б U , ... , х б ( у + 1 ) - 1 ) я < л ( J я х JJ B я NбК-1NжурналNφ справедливы для любогоn-набораt0,,tn-1[0,b], где для любогоj=bu+j,0j<b, мы определяем Nj=T b - 1 t u (xbu,,xbu
(*)U<N'TTUб(ИксбU,...,Иксб(U+1)-1)я<L(JAяИксJJВяNJ)
N'T0,...,TN'-1[0,б]Jзнак равнобU+J'0J'<б
NJзнак равноTTUб-1(ИксбU,...,ИксбU+J'-1,ИксбU+J'+1,...,Иксб(U+1)-1),
TTбО(2б)(*)О(N2б)NJО(2б)О(2Кб)О(L2Кб)(*) является примером нашей проблемы размера О(L2О(Кб)) в Nпеременные. По предположению, мы можем проверить его действительность во времениО(2δN+О(Кб)LО(1)), Мы повторяем эту проверку для всехбN' выбор TТаким образом, общее время
О((б+1)N/б2δN+О(Кб)LО(1))знак равноО(2δN+О(КNжурналN)LО(1))
как утверждено.

Мы получаем более тесную связь с (S) ETH, рассматривая версию задачи с ограниченной шириной: для любого К3, позволять К-MonImp обозначает ограничение проблемы, где Φ это К-CNF и Ψ это К-DNF. (S) ETH касается констант

sКзнак равноинф{δ:К-SATDTяMЕ(2δN)},sзнак равновир{sК:К3},
Аналогично, давайте определимся
sК'знак равноинф{δ:К-MоNямпDTяMЕ(2δN)},s'знак равновир{sК':К3},
Очевидно, что
s3's4's'1
как в случае SAT. У нас также есть
sК'sК,
и уменьшение двойной переменной в вопросе показывает
sК2sК',
Теперь, если мы применим конструкцию выше с постоянным размером блока б, мы получаем
sКsбК'+журнал(б+1)б,
следовательно
sзнак равноs',
В частности, SETH эквивалентен s'знак равно1и ETH эквивалентно sК'>0 для всех К3,
Эмиль Йержабек поддерживает Монику
источник
Спасибо за ваш ответ! Мне интересно, можно ли сделатьΦ и Ψпостоянная глубина в этой конструкции? А именно, я не знаю, известны ли монотонные логические формулы постоянной глубины субэкспоненциального размера (или даже немонотонные схемы) дляTКN(в частности, для большинства)? Конечно есть2NΩ(1/d) нижняя граница для глубиныdно, скажем, 2Nразмер будет в порядке.
Саша Козачинский
TКNи вообще все, что можно вычислить по формулам полиномиального размера (т. е. в NC ^ 1), имеетd схемы размера 2NО(1/d), См. Например, cstheory.stackexchange.com/q/14700 . Мне придется подумать, сможешь ли ты сделать их монотонными, но это звучит правдоподобно.
Эмиль Йержабек поддерживает Монику
OK. Во-первых, универсальная конструкция прекрасно работает в монотонной настройке: если функция имеет монотонные формулы разного размера, она имеетd монотонные схемы размера 2NО(1/d)поLY(N) для любого d2, Во-вторых, дляTКN в частности, легко построить монотонную глубину3 схемы размера 2О(NжурналN) разделив входные данные на блоки размера Θ(NжурналN),
Эмиль Йержабек поддерживает Монику
На самом деле, продвигая эту идею немного больше, она дает ответ на первоначальный вопрос: предполагая, что SETH, нижняя граница сохраняется для Φ монотонный CNF и Ψмонотонный DNF. Я напишу это позже.
Эмиль Йержабек поддерживает Монику
Я думаю, что вы можете разделить все переменные примерно на N блоки Икс1,...ИксN а потом пишешь TК1N(Икс1)...TКNN(ИксN)φ' для каждого К1+...+КNN, Ты можешь использовать2Nразмер CNF для каждой пороговой функции. Но тогда с правой стороны у вас будет не DNF, а формула глубины 3 ...
Саша Козачинский