Теорема о прямой сумме для пространственной сложности предложения Резолюции?

Резолюция - это схема, доказывающая неудовлетворенность CNF. Доказательством в резолюции является логический вывод пустого предложения для начальных предложений в CNF. В частности, любой начальный пункт может быть выведен, и из двух пунктов и также может быть выведен пункт Опровержение - это последовательность выводов, которая заканчивается пустым предложением. $A \lor x$ $B \lor \neg{x}$ $A \lor B$

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

Пусть $Sp(F)$ наименьшее количество предложений, которые должны храниться в памяти, чтобы достичь пустых предложений. Это называется раздел пространства сложность $F$ . Скажем, что $Sp(F)=\infty$ является $F$ выполнимым.

Проблема, которую я предлагаю, заключается в следующем: рассмотрим два CNF и , и пусть CNF $A=\bigwedge_{i=1}^m A_i$ $B=\bigwedge_{j=1}^n B_j$

A \lor B = ⋀_{i = 1}^{m} ⋀_{j = 1}^{n} A_{i} \lor B_{j}

$A \lor B = \bigwedge_{i=1}^m \bigwedge_{j=1}^n A_i \lor B_j$

Какова связь $Sp(A \lor B)$ с $Sp(A)$ и $Sp(B)$ ?

Очевидной верхней границей является $Sp(A \lor B) \leq Sp(A) + Sp(B) -1$ . Это туго?

cc.complexity-theory lo.logic proof-complexity proof-search MassimoLauria
источник

Хороший вопрос! Вы знаете ответ по размеру прямой суммы? Я предполагаю, что худший случай, когда A и B не имеют общих переменных. Интересный случай может быть, когда A и B одинаковы вплоть до переименования переменной. Кстати, я не вижу, как вы получаете эту верхнюю границу, кажется, что это может быть намного хуже.

Каве

B

$B$

A_{i} \lor B_{j}

$A_i \lor B_j$

1 \leq j \leq n

$1 \leq j \leq n$

A_{i}

$A_i$

1 \leq i \leq m

$1 \leq i \leq m$

A

$A$

m . (S i z e (B) + O (1)) + S i z e (A)

$m.(Size(B)+O(1))+Size(A)$ ,

Каве

F_{1} \lor F_{2} \lor \dots F_{k}

$F_1 \lor F_2 \lor \ldots F_k$

F_{i}

$F_i$

F

$F$

L e n g t h (A \lor B) \leq L e n g t h (B) | A | + L e n g t h (A)

$Length(A \lor B) \leq Length(B)|A|+Length(A)$

Верхняя граница тривиального пространства на самом деле требует еще одного предложения в памяти. Я отредактировал соответственно.

MassimoLauria

Ответы:

Я хотел опубликовать это как комментарий, но так как я не могу понять, как это сделать, я думаю, что вместо этого это будет «ответ».

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

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

Вопрос касается длины опровержения. Кажется разумным полагать, что ограничение длины, указанное в комментарии Массимо, является жестким, но знаем ли мы это?

$A$ $B_i$ $w_A$ $B$ $B$ $w_B$ $\max (w_A, w_B)$

Это, конечно, легкое наблюдение, но дело в том, что это может указывать на то, что вопрос о космосе может быть сложным. Это так, поскольку почти все нижние границы пространства в опровержении, о которых мы знаем, проходят через нижние границы ширины. (То есть нижние границы пространства были получены независимо, но, оглядываясь назад, все они следуют в качестве следствия из красивой статьи «Комбинаторная характеристика ширины разрешения» Ацериаса и Далмау.) Но если для предложения по разрешению есть теорема о прямой сумме пространство, оно не будет следовать из нижних границ ширины, но должно обсуждаться напрямую, что, по крайней мере, до сих пор казалось гораздо сложнее. Но, конечно, может быть какой-то простой аргумент, который я пропускаю.

Якоб Нордстрем
источник

Добро пожаловать, Якоб!

Арнаб

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

Суреш Венкат

Привет, Джейкоб, приятно видеть тебя здесь. (ps: я думаю, что вы преодолели порог.)

Kaveh

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

MassimoLauria