Nachweisbare Lücken zwischen Entscheidungsbaumkomplexität und „wahrer“ Komplexität

Der Titel ist ein bisschen irreführend, aber die Frage ist hoffentlich nicht:

Grønlund und Pettie das neue Ergebnis zeigt , dass 3sum nur Entscheidungsbaum Komplexität hat mich gefragt: $O(n^{3/2})$

Gibt es ein einfaches Beispiel für ein Problem mit einer Entscheidungsbaumkomplexität von , das jedoch eine untere Schranke (in einem detaillierteren Modell) von zulässt ? $O(f)$ $\omega(f)$

Mit anderen Worten, wie sollte das Ergebnis auf 3SUM unsere Sicht auf die Möglichkeit ändern, eine Obergrenze für die Komplexität des Problems zu erreichen , die deutlich unter ? $n^2$

cc.complexity-theory machine-models decision-trees Suresh Venkat
quelle

Die Elementunterscheidbarkeit kann mit einem binären Entscheidungsbaum mit konstanter Tiefe gelöst werden. ("Unterscheiden sich alle Elemente?") Wir benötigen jedoch eine Tiefe von

, um das Problem unter Verwendung linearer Entscheidungsbäume zu lösen .

Ω (n \log n)

$\Omega(n\log n)$

Jeffs

Das Entscheidungsbaummodell ist ein informationstheoretisches Modell: Wenn Sie genügend Informationen über Ihre Eingabe erhalten haben, so dass die Antwort eindeutig aus diesen Informationen bestimmt wird, sind Sie fertig. Es spielt keine Rolle, ob die Bestimmung der Antwort aus diesen Informationen unentscheidbar ist. Wenn die Eingabe beispielsweise eine n-Bit-Binärzeichenfolge ist, die eine Turing-Maschine codiert, und die Frage lautet, ob diese TM anhält, kann ein Entscheidungsbaum der Tiefe n dieses Problem trivial lösen, da er alle n Bits kennt, aber keinen Algorithmus lösen kann dieses Problem.

Robin Kothari

Vielleicht hätte ich stattdessen 'Beispiel für ein einfaches Problem' sagen sollen :).

Suresh Venkat

Antworten:

Meyer auf der Heide beschrieb eine nicht einheitliche Familie linearer Entscheidungsbäume für die Teilmenge Summe mit der Tiefe . Ein ähnliches Ergebnis kann aus einem späteren Algorithmus von Meiser für die Punktlokalisierung in Hyperebenenanordnungen abgeleitet werden. Natürlich ist das Problem NP-schwer. $O(n^4\log n)$

Jeffε
quelle

Wenn ich WIRKLICH PEDANTISCH sein wollte, würde ich darauf hinweisen, dass NP-hart keine feste Untergrenze ist. Aber das ist ein gutes Beispiel für den Geist dessen, wonach ich suche.

Suresh Venkat

Ja, aber wir wissen nicht, wie wir feste Untergrenzen beweisen sollen.

Jeffs

@ Jɛ ɛ E Kennen Sie vielleicht eine schöne Zusammenfassung oder Darstellung dieses Ergebnisses? Ich finde es sehr schwer, dem Original zu folgen, einige Definitionen sind mir überhaupt nicht klar.

Domotorp

Zumindest die grundlegenden Definitionen sind in meinem Aufsatz über lineare Entartungsprobleme beschrieben .

Jeffs

Hier ist ein Beispiel für eine triviale Lücke zwischen Entscheidungsbaum und algorithmischer Komplexität. Die randomisierte Entscheidungsbaumkomplexität der lokalen Sortierung (Orientierung eines vertexgewichteten Graphen) ist $O(n\log(\frac{m+n}{n}))$ $\Theta(n+m)$ $m=\omega(n)$

Seth Pettie
quelle

Lassen Sie mich ein wenig widersprechen. Im RAM-Modell müssen wir nicht unbedingt die gesamte Eingabe lesen. Im Turing-Maschinenmodell gibt es viele triviale Probleme, die mit einem Entscheidungsbaum (oder auf einer RAM-Maschine) schneller gelöst werden können. Siehe auch Robins Kommentar zur ursprünglichen Frage.

Domotorp