Problemy do zredukowania w celu udowodnienia dolnej granicy

Jakie są standardowe problemy, które możemy zredukować, aby udowodnić dolne granice ?$\Omega(n\log n)$

Oczywiście problemy ze stanem inne niż sortowanie i rozróżnianie elementów.

Ben-Or bezpośrednio udowodnił dolne granice log n ) dla kilku podstawowych problemów w modelu drzewa obliczeń algebraicznych:$\Omega(n\log n)$

• Odróżnienie elementów: czy przy uwzględnieniu tablicy liczb rzeczywistych, czy jej elementy są różne?$n$
• Zestaw rozłączności: Biorąc pod uwagę dwa zestawy liczb rzeczywistych, czy mają one wspólny element?$n$
• Ustaw równość: Biorąc pod uwagę dwa zestawy liczb rzeczywistych, czy jedna tablica jest permutacją drugiego?$n$
• Zmierz problem: biorąc pod uwagę realnych odstępach, co jest całkowitą długością ich związku?$n$
• Włączenie zestawu: czy biorąc pod uwagę dwa zestawy liczb rzeczywistych, czy jeden jest podzbiorem drugiego?
• Parytet permutacji: biorąc pod uwagę permutację zbioru , czy permutacja jest parzysta czy nieparzysta?$[n]$

Pierwsze trzy są najczęściej stosowane w geometrii obliczeniowej.