Complexidade de decidir se uma família é uma família de Sperner

16

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.FmFO(nm)

SXYSXYY XXYYX

Anthony Leverrier
fonte
Então você está perguntando se existe um limite superior de nm?
precisa
Basicamente sim. Na verdade, eu gostaria de provar que não existe nenhum algoritmo que possa ter sucesso (na pior das hipóteses) com complexidade O (mn).
Anthony Leverrier
Como os subconjuntos são fornecidos? "Matriz de adjacência" ou "lista de margens"?
Yuval Filmus
A entrada é uma matriz de adjacência.
Anthony Leverrier
9
+1 por tentar nos fazer resolver o problema de multiplicação de matrizes sem perceber. :-) #
315 Peter Shor

Respostas:

16

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 TS1S2SmAm×nAij=1jSiBm×nBij=1jSiABTtem uma entrada se e somente se houver um conjunto de F contido em outro.0F

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)

Peter Shor
fonte