Kompleksitas memutuskan apakah keluarga adalah keluarga Sperner

Kita diberi keluarga dari himpunan bagian dari {1, ..., n}. Apakah mungkin untuk menemukan batas bawah non-sepele pada kompleksitas memutuskan apakah adalah keluarga Sperner? Batas bawah sepele adalah dan saya sangat curiga bahwa itu tidak ketat.$\mathcal{F}$$m$$\mathcal{F}$$O(n m)$

Ingatlah bahwa himpunan adalah keluarga Sperner jika untuk dan di ; menyiratkan bahwa dan . X Y S X ≠ Y X ⊈ Y Y ⊈ $\mathcal{S}$$X$$Y$$\mathcal{S}$$X \ne Y$$X \nsubseteq Y$$Y \nsubseteq X$

Tidak bisakah Anda menyelesaikan ini dengan perkalian matriks? Biarkan set menjadi , S 2 , ... , S m . Ambil matriks A menjadi matriks m × n di mana A i j = 1 jika j ∈ S i dan 0 sebaliknya, dan B menjadi matriks m × n di mana B i j = 1 jika j ∉ S i dan 0 sebaliknya. Sekarang, 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$memiliki entri jika dan hanya jika ada satu set F yang terkandung dalam yang lain.$0$$\mathcal{F}$

Jadi jika Anda membuktikan batas bawah untuk kasus di mana m = θ ( n ) , Anda telah membuktikan batas bawah yang sama untuk perkalian matriks. Ini adalah masalah terbuka yang terkenal.$\Omega(n^{2+\epsilon})$$m = \theta(n)$

Saya belum banyak berpikir tentang itu, tapi saya tidak melihat cara Anda dapat membuktikan bahwa kasus perkalian matriks ini pada dasarnya sekeras kasus umum; jika Anda benar-benar membutuhkan batas bawah, ini tampaknya menjadi satu-satunya harapan yang Anda miliki untuk membuktikannya tanpa menyelesaikan masalah perkalian matriks.

Di sisi positifnya, ini memberikan algoritma untuk masalah ini yang lebih baik daripada algoritma naif yang mengambil .$\theta(m^2n)$