Komplexität der Entscheidung, ob eine Familie eine Sperner-Familie ist

Wir bekommen eine Familie von$\mathcal{F}$$m$ Teilmengen von {1, ..., n}. Ist es möglich, eine nicht triviale Untergrenze für die Komplexität der Entscheidung zu finden, ob $\mathcal{F}$ eine Sperner-Familie ist? Die triviale Untergrenze ist $O(n m)$ und ich vermute stark, dass es nicht eng ist.

Denken Sie daran, dass eine Menge $\mathcal{S}$ eine Sperner-Familie ist, wenn für und in ; impliziert, dass und Y \ nsubseteq X sind .$X$$Y$$\mathcal{S}$$X \ne Y$$X \nsubseteq Y$$Y \nsubseteq X$

Können Sie dies nicht durch Matrixmultiplikation lösen? Sei die Menge , , , . Man nehme Matrix A als m × n- Matrix, wobei A i j = 1 ist, wenn j ≤ S i und 0 ist, und B als m × n- Matrix, wobei B i j = 1 ist, wenn j ≤ S i und 0 ist. Nun hat A B T a$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$ Eintrag genau dann, wenn ein Satz von F in einem anderen enthalten ist.$0$$\mathcal{F}$

Wenn Sie also eine Untergrenze von für den Fall beweisen, dass m = θ ( n ) ist , haben Sie die gleiche Untergrenze für die Matrixmultiplikation bewiesen. Dies ist ein bekanntes offenes Problem.$\Omega(n^{2+\epsilon})$$m = \theta(n)$

Ich habe nicht viel darüber nachgedacht, aber ich sehe keine Möglichkeit, zu beweisen, dass dieser spezielle Fall der Matrixmultiplikation im Wesentlichen so schwierig ist wie der allgemeine Fall. Wenn Sie wirklich eine Untergrenze benötigen, scheint dies die einzige Hoffnung zu sein, die Sie haben, um eine zu beweisen, ohne das Matrixmultiplikationsproblem zu lösen.

Auf der positiven Seite gibt dies Algorithmen für dieses Problem, die besser sind als der naive Algorithmus, der .$\theta(m^2n)$