Problemas para reduzir de para provar um limite inferior

Quais são os problemas padrão dos quais podemos reduzir para provar limites inferiores?$\Omega(n\log n)$

Obviamente, declare outros problemas além de classificação e distinção de elementos.

Ben-Or provou diretamente limites inferiores para vários problemas fundamentais no modelo de árvore de computação algébrica:$\Omega(n\log n)$

• $n$
• $n$
• $n$
• $n$
• Inclusão de conjuntos: dados dois conjuntos de números reais, um é um subconjunto do outro?
• $[n]$

Os três primeiros são os mais usados ​​em geometria computacional.