Сложность решения, является ли семья спернеров

Нам дано семейство из подмножеств {1, ..., n}. Можно ли найти нетривиальную нижнюю оценку сложности решения, является ли семейством Спернера? Тривиальная нижняя граница - и я сильно подозреваю, что она не жесткая.$\mathcal{F}$$m$$\mathcal{F}$$O(n m)$

Напомним, что множество является семейством Спернера, если для и в ; означает , что и .$\mathcal{S}$$X$$Y$$\mathcal{S}$$X \ne Y$$X \nsubseteq Y$$Y \nsubseteq X$

Вы не можете решить это с помощью умножения матриц? Пусть наборы будут , , , . Принять матрицу за матрицу где если и 0 в противном случае, а за за матрицу где если и 0 иначе Теперь, имеет запись тогда и только тогда, когда есть один набор содержащийся в другом. 0 $S_1$$S_2$$\ldots$$S_m$$A$$m \times n$$A_{ij}=1$$j \in S_i$$B$$m \times n$$B_{ij}=1$$j \notin S_i$$AB^T$$0$$\mathcal{F}$

Поэтому, если вы докажете нижнюю границу для случая, когда , вы подтвердите ту же нижнюю границу для умножения матриц. Это известная открытая проблема.m = θ ( n $\Omega(n^{2+\epsilon})$$m = \theta(n)$

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

С другой стороны, это дает алгоритмы для этой задачи, которые лучше, чем простой алгоритм, который принимает .$\theta(m^2n)$