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.

cc.complexity-theory lower-bounds

— Vinayak Pathak
źródło

W jakim modelu obliczeniowym?

— Mahdi Cheraghchi,

Słuszna uwaga. Miałem na myśli model oparty na porównaniu.

— Vinayak Pathak,

Ben-Or bezpośrednio udowodnił dolne granice 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.

— Jeffε
źródło

bez znaczenia: pierwsze trzy są również trudnymi kanonicznymi problemami dla dolnych granic algorytmu strumienia opartego na złożoności komunikacji.

— Suresh Venkat,

@SureshVenkat - Widziałem ustawione rozłączność i równość używane do udowodnienia niższych granic w streamingu. Czy masz przykład odrębności elementów?

— Vinayak Pathak,

Przynajmniej jedno miejsce, które widziałem, znajdowało się w analizie algorytmów w modelu W-stream. Ogólnie rzecz biorąc, ED jest ściśle związany z rozłącznością wektora bitowego (lub zestawu)

— Suresh Venkat,