Złożoność decydowania, czy rodzina jest rodziną Sperner

Otrzymujemy rodzinę składającą się z m podzbiorów {1, ..., n}. Czy można znaleźć nietrywialną dolną granicę złożoności decydowania, czy F jest rodziną Spernerów? Trywialna dolna granica to O ( n m ) i mocno podejrzewam, że nie jest ciasna.$\mathcal{F}$$m$$\mathcal{F}$$O(n m)$

Przypomnij sobie, że zestaw jest rodziną Spernerów, jeśli dla X i Y w S ; X ≠ Y wynika, że X ⊈ Y i Y ⊈ X .$\mathcal{S}$$X$$Y$$\mathcal{S}$$X \ne Y$$X \nsubseteq Y$$Y \nsubseteq X$

Nie możesz rozwiązać tego przez mnożenie macierzy? Niech zbiory będą , S 2 , … , S m . Wziąć macierzy A się do m x n macierzy, gdy i j = 1 , jeżeli J ∈ S : i i 0 inaczej, a B się na m × n macierzy, gdzie B i j = 1 , jeżeli J ∉ S : i i 0 inaczej. Teraz A B $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$ma pozycję wtedy i tylko wtedy, gdy jeden zestaw F jest zawarty w innym.$0$$\mathcal{F}$

Jeśli więc udowodnisz dolną granicę w przypadku, gdy m = θ ( n ) , udowodniłeś tę samą dolną granicę dla mnożenia macierzy. To słynny otwarty problem.$\Omega(n^{2+\epsilon})$$m = \theta(n)$

Nie zastanawiałem się nad tym zbyt wiele, ale nie widzę żadnego sposobu, aby udowodnić, że ten konkretny przypadek mnożenia macierzy jest zasadniczo tak trudny jak ogólny przypadek; jeśli naprawdę potrzebujesz dolnej granicy, wydaje się, że jest to jedyna nadzieja na udowodnienie jej bez rozwiązania problemu mnożenia macierzy.

Na plus daje to algorytmy tego problemu, które są lepsze niż naiwny algorytm, który zajmuje .$\theta(m^2n)$