Recebemos uma família de m subconjuntos de {1, ..., n}. É possível encontrar um limite inferior não trivial à complexidade de decidir se F é uma família Sperner? O limite inferior trivial é O ( n m ) e eu suspeito fortemente que ele não seja rígido.
Y ⊈ X
ds.algorithms
co.combinatorics
Anthony Leverrier
fonte
fonte
Respostas:
Você não pode resolver isso por multiplicação de matrizes? Deixe os conjuntos serem , S 2 , … , S m . Considere a matriz A como a matriz m × n onde A i j = 1 se j ∈ S i e 0 caso contrário, e B como a matriz m × n onde B i j = 1 se j ∉ S i e 0 caso contrário. Agora, A B TS1 1 S2 ... Sm A m×n Aij=1 j∈Si B m×n Bij=1 j∉Si ABT tem uma entrada se e somente se houver um conjunto de F contido em outro.0 F
Portanto, se você provar um limite inferior de para o caso em que m = θ ( n ) , você provou o mesmo limite inferior para multiplicação de matrizes. Este é um famoso problema aberto.Ω(n2+ϵ) m=θ(n)
Não pensei muito nisso, mas não vejo como você possa provar que esse caso particular de multiplicação de matrizes é essencialmente tão difícil quanto o caso geral; se você realmente precisa de um limite inferior, esta parece ser a única esperança que você tem de provar um sem resolver o problema de multiplicação da matriz.
No lado positivo, isso fornece algoritmos para este problema que são melhores que o ingênuo que leva .θ(m2n)
fonte