Какой самый быстрый способ проверить наличие набора?

Даны $n$ подмножеств $S_1,\ldots,S_n$ из $\{1,\ldots,d\}$ .

Проверьте, есть ли множества $S_i,S_j$ с $S_i \subsetneq S_j$ . (Если так, найдите пример, если нет, просто скажите «нет»)

Тривиальное решение этой проблемы проходит через все пары наборов и проверяет включение для пары за время $O(d)$ , поэтому общее время выполнения равно $O(n^2 d)$ . Можно ли решить эту проблему быстрее? Есть ли название для этого в литературе?

Вы не можете решить это за $O(n^{2-\epsilon})$ время для любой константы $\epsilon>0$ если гипотеза сильного экспоненциального времени не ложна.

То есть, если бы мы имели такой алгоритм, мы могли бы решить $n$ -переменной CNF выполнимость в $O((2-\epsilon')^{n})$ время для некоторых $\epsilon'>0$ . Причина в том, что мы могли бы разделить переменные на две равные части $P_1$ и $P_2$ из $n/2$ переменных каждая. Для каждой части построим семейство $F_1$ и $F_2$соответственно подмножества пунктов следующим образом. Для каждого назначения мы добавляем подмножество, состоящее из пунктов, не удовлетворяемых назначением. Эта конструкция работает в $poly(n)2^{n/2}$ раз.

Чтобы завершить построение, отметим, что исходный экземпляр CNF имеет решение, если в имеется подмножество, $F_1$которое не пересекается с некоторым подмножеством в $F_2$ .

Добавляя некоторые дополнительные элементы к вашему основному набору в дополнение к элементам для каждого предложения, не так уж сложно встроить эту проблему непересекаемости в вопрос включения множеств. Вы в основном берете дополнения к подмножествам в . Чтобы убедиться, что два набора в F 1 не считаются включением, вы добавляете код из анти-цепочки на дополнительные элементы. Другой антицепочечный код (на других дополнительных элементах основного набора) используется в подмножествах F 2, чтобы убедиться, что никакие пары подмножеств из F 2 не образуют включения. Наконец, все множества, сформированные из F 1, включают в себя все элементы антицепочечных кодов F 2 .$F_1$$F_1$$F_2$$F_2$$F_1$$F_2$

Это вопрос включения набора в подмножества на d = p o l y ( n ) основном множестве. Аргумент в основном восходит к какой-то ранней работе Райана Уильямса (не помню, какой именно).$2^{n/2+1}$$d=poly(n)$

Если вас интересуют семейства множеств с , то другое решение, концептуально очень похожее на то, которое было изложено в ответе Ювала, - это вычисление дзета-преобразования.$n = \omega(2^{d/2})$

$$f\zeta(T) = \sum_{S \subseteq T} f(S)\,,$$

где - функция индикатора входного семейства F = { S 1 , S 2 , … , S n } . То есть f ( S ) = 1, если S ∈ F и f ( S ) = 0 в противном случае. Ясно, что существуют множества S i ≠ S j такие, что S i ⊆ $f \colon 2^{[d]} \to \mathbb{R}$$\mathcal{F} = \{ S_1, S_2, \dotsc, S_n \}$$f(S) = 1$$S \in \mathcal{F}$$f(S) = 0$$S_i \not= S_j$ тогда и только тогдакогда F ζ ( S ) > 1 для некоторого S ∈ F .$S_i \subseteq S_j$$f\zeta(S) > 1$$S \in \mathcal{F}$

Дзета-преобразование может быть вычислено за время с использованием алгоритма Йейтса, см., Например, Knuth's TAOCP, vol. 2, §4.6.4. Сам алгоритм представляет собой довольно простое динамическое программирование, и его легко изменить, чтобы привести пример включенного набора, если таковой существует.$O(d2^d)$

Эта проблема может быть решена с помощью алгоритма быстрого умножения матриц, и я также подозреваю, что он вычислительно эквивалентен умножению матриц (хотя я не знаю ни одного способа доказать это, и я не думаю, что методы для доказательства этого существуют ). Это решение будет иметь время выполнения O (n ^ {2.373}), когда n = d, и другое время выполнения для других отношений между d и n.

Вот как вы решаете это с помощью умножения матриц: Вы записываете характеристические векторы наборов в строках матрицы n на d матрицы A, а характеристические векторы дополнений наборов в столбцах ad на n матрицы B. Вы затем умножьте A на B. Пары множеств, которые пересекаются, являются точными местоположениями произведения A * B, равными нулю.

Для лучшего времени выполнения, известного для этой проблемы, см. Статью Хуана и Пана на эту тему. Если я правильно помню, когда d станет достаточно большим, время выполнения станет очевидно оптимальным O (nd). Для n = d у вас будет время работы O (n ^ {2.373}). Для других отношений n и d вы получите другие значения. Если существует оптимальный алгоритм для умножения прямоугольной матрицы, вы получите алгоритм с временем выполнения O (n ^ 2 + nd) для вашей задачи. Я подозреваю, что нет лучшего способа, чем этот, чтобы решить вашу проблему, но я далеко не уверен.

Это решение, вероятно, не имеет практического применения, поскольку константы этих алгоритмов слишком велики. Алгоритм Штрассена может дать улучшение по сравнению с наивным решением для разумных значений n и d, но я даже не уверен в этом. Тем не менее, проблемы, которые кажутся связанными с умножением матриц, редко имеют комбинаторные алгоритмы, которые лучше, чем наивный алгоритм (больше, чем полилогарифмические факторы), поэтому, если бы мне пришлось угадывать, я бы предположил, что для вашей задачи не существует хорошего алгоритма, который значительно лучше, чем наивный, используя современные методы.

$n > \binom{d}{d/2} \approx \frac{2^d}{\sqrt{\pi d/2}}$$n$

$f$$[m]$$O(m2^m)$$f$$f$

$$\Sigma = \sum_{x,y \in f} S(x,y),$$ $S(x,y) \geq 0$$x,y$$S(x,y)$$\{(x_i,y_i) : i \in [d]\}$$x_i$$i \in x$

$f,g$$\Sigma = \sum_{x\in f, y\in g} S(x,y)$$p$$f,g$$p \in (0,1/2)$$\Sigma = \sum_x T(x) \hat{f}(x) \hat{g}(x)$$T(x)$$x$

$$F = \{ S_i \cup \{x\} : i \in [n] \} \cup \{ \overline{S_i} \cup \{y\} : i \in [n] \}.$$ $S_i \cup \{x\}$$\overline{S_i} \cup \{y\}$$S(x,y)$$\Sigma$$S_i \cup \{x\}$$\overline{S_j} \cup \{y\}$$S_i \cap \overline{S_j} = \emptyset$$S_i \subseteq S_j$$S_1,\ldots,S_n$ $$\Sigma = \sum_{i=1}^n S(S_i \cup \{x\}, \overline{S_i} \cup \{y\}).$$

$\tilde{O}(n + 2^d)$$d$$n$$2^d$$\tilde{O}(n^2)$$n = \omega(2^{d/2})$

$S_i \subseteq S_j$$S_1,\ldots,S_n$$G_1,G_2$$1/2$$S_i$$S_j$$G_1$$G_2$$O(\log n)$$S_i \subseteq S_j$

$n = 2^k$$k$$x$$y$$O(nd)$$O(\log^2 n)$