Zu reduzierende Probleme, um eine untere Schranke von

Welche Standardprobleme können wir reduzieren, um -Untergrenzen zu beweisen ? $\Omega(n\log n)$

Natürlich gibt es andere Probleme als das Sortieren und die Unterscheidbarkeit der Elemente.

cc.complexity-theory lower-bounds Vinayak Pathak
quelle

In welchem Rechenmodell?

MCH

Guter Punkt. Ich meinte das Vergleichsmodell.

Vinayak Pathak

Antworten:

Ben-Or hat die unteren Grenzen von für verschiedene grundlegende Probleme im algebraischen Berechnungsbaummodell direkt bewiesen : $\Omega(n\log n)$

$n$
$n$
$n$
$n$
Set-Inklusion: Ist eine der beiden reellen Zahlen eine Teilmenge der anderen?
$[n]$

Die ersten drei werden am häufigsten in der Berechnungsgeometrie verwendet.

Jeffε
quelle

Nebenbei bemerkt: Die ersten drei sind auch die kanonischen Hauptprobleme für die unteren Grenzen des auf Kommunikationskomplexität basierenden Stream-Algorithmus.

Suresh Venkat

@ SureshVenkat - Ich habe gesehen, wie Disjunktheit und Gleichheit festgelegt wurden, um untere Grenzen beim Streaming zu beweisen. Haben Sie ein Beispiel für die Unterscheidbarkeit von Elementen?

Vinayak Pathak

Mindestens eine Stelle, die ich sah, war die Analyse von Algorithmen unter dem W-Stream-Modell. Im Allgemeinen hängt ED eng mit der Disjunktion von Bitvektoren (oder Mengen) zusammen

Suresh Venkat,