Komplexitätsuntergrenze: Die Lücke zwischen Entscheidungsbäumen und RAMs

15

Ich habe kürzlich eine quadratische Untergrenze für die Komplexität eines Problems im Entscheidungsbaummodell entdeckt, und ich frage mich, ob dieses Ergebnis teilweise auf das Zufallszugriffsmaschinenmodell verallgemeinert werden kann. Durch teilweise , meine ich eine Verallgemeinerung Programme auf RAM mit einem bestimmten Zeit / Raum - Kompromiss. Zum Beispiel möchte ich zeigen, dass mein Problem nicht durch ein RAM-Programm für lineare Zeit und Raum gelöst werden kann.

AM Ben-Amram und Z. Galil haben in dieser Arbeit bewiesen , dass ein RAM-Programm, das in Zeit und Raum s abläuft, in O ( t simuliert werden kannts Zeit auf einer Zeigermaschine. Kennen wir ähnliche Ergebnisse, die auf Entscheidungsbäume angewendet werden könnten?Ö(tLogs)

Ist es alternativ möglich, ein RAM-Programm, das im Raum mit einem Entscheidungsbaum des Grades s zu simulieren ? (Intuitiv kann die indirekte Adressierung mit Knoten s simuliert werden )sss

Totoro
quelle
Ich weiß nicht viel über die klassische Abfragekomplexität (Entscheidungsbaumkomplexität), aber wenn Sie im analogen Modell in einer Quanteneinstellung (Quantenabfragekomplexität) arbeiten, erhalten Sie manchmal ziemlich schlechte Untergrenzen für das Schaltungsmodell. Zum Beispiel können Sie für HSP zeigen, dass die Abfragekomplexität polynomisch ist, aber die Einheiten zwischen den Abfragen nehmen eine exponentielle Anzahl von Gates an ... und soweit wir vermuten, ist die allgemeine HSP in polynomischer Zeit nicht möglich, sodass die Abfragekomplexität nur gegeben ist sehr lockere untere Schranken. Oder geht es dir gut mit einer sehr lockeren Untergrenze?
Artem Kaznatcheev
Eigentlich würde ich gerne eine superlineare Untergrenze für (einige) Programme bekommen, die im RAM laufen. Deshalb habe ich gehofft, dass die Einschränkung der Raumkomplexität helfen könnte.
Totoro
1
Ich verstehe deine Frage nicht. Wie kann eine quadratische Untergrenze für die Komplexität von Abfragen festgelegt werden? Außerdem verwenden Zeit-Raum-Kompromisse häufig direkte Produkttheoreme, sodass Sie möglicherweise härter arbeiten müssen, um solche Ergebnisse zu erzielen.
Hartmut Klauck
1
Die Komplexitätsuntergrenze im Entscheidungsbaummodell ergibt sich aus einer Untergrenze für die Anzahl der möglichen Ausgaben des Problems (deren Logarithmus eine Untergrenze für die Höhe des Baums liefert).
Totoro

Antworten:

10

Das natürliche Modell für Entscheidungsbäume, mit denen RAMs simuliert werden können, ist das Verzweigungsprogramm. Grundsätzlich handelt es sich um einen Entscheidungsbaum mit gemeinsamen Teilbäumen, die zu einer DAG zusammengefasst wurden. Zeit T und Raum S in einem RAM können in Höhe T und Größe 2 ^ S in einem Verzweigungsprogramm simuliert werden. (Möglicherweise müssen Sie die Mehrfachverzweigung verwenden.)

Für Entscheidungsprobleme ist klar, dass jeder Entscheidungsbaum nur Eingaben für height = # und space = total # of bits in der Eingabe benötigt. Beachten Sie, dass bei einer Mehrfachverzweigung die Anzahl der Bits in der Eingabe möglicherweise größer ist als das übliche Maß für die Anzahl der Eingaben (z. B. n Zeiger, die jeweils log n Bits aufnehmen). Für solche Probleme mit nlog n Gesamteingabebits kann man dies beweisen Bestimmte Probleme können nicht in Zeit O (n) und Leerzeichen = O (n) Bits gelöst werden. Ist das die Form von dir Problem?

Sie scheinen vorzuschlagen, dass Sie die Anzahl der Ausgaben verwenden, um eine größere Untergrenze zu erhalten. Bei Problemen mit mehreren Ausgaben ist es üblich, dass viele Ausgaben entlang einer einzelnen Kante und nicht an Blattknoten möglich sind (siehe beispielsweise Borodin-Cooks Aufsatz von 1982 zum Sortieren von Untergrenzen). Aber auch ohne diese Annahme kann man jede Funktion mit den Eingabebits height = # und space = # berechnen. (Lesen und merken Sie sich die Eingabe und geben Sie alle Werte an jedem Blattknoten aus.)

Paul Beame
quelle
Vielen Dank für Ihre Antwort. Die Eingabe des Problems ist eine Sammlung von ganzen Zahlen, so dass davon ausgegangen werden kann, dass sie als Listen angegeben werden. Wie auch immer, danke, dass Sie auf Borodins und Cooks Technik hingewiesen haben (ich wusste es überhaupt nicht). Ich hoffe, dass diese Art von Methode auf mein Problem angewendet werden kann.
Totoro
1

Das natürliche Modell für Entscheidungsbäume, das RAMs verlustfrei simuliert, ist das Verzweigungsprogramm. Grundsätzlich handelt es sich um einen Entscheidungsbaum mit gemeinsamen Teilbäumen, die zu einer DAG zusammengefasst wurden. Zeit T und Raum S in einem RAM können in Höhe T und Größe 2 ^ S in einem Verzweigungsprogramm simuliert werden. (Möglicherweise müssen Sie die Mehrfachverzweigung verwenden.)

Für Entscheidungsprobleme ist klar, dass jeder Entscheidungsbaum nur Eingaben für height = # und space = total # of bits in der Eingabe benötigt. Beachten Sie, dass bei einer Mehrfachverzweigung die Anzahl der Bits in der Eingabe möglicherweise größer ist als das übliche Maß für die Anzahl der Eingaben (z. B. n Zeiger, die jeweils log n Bits aufnehmen). Für solche Probleme mit nlog n Gesamteingabebits kann man dies beweisen Bestimmte Probleme können nicht in Zeit O (n) und Leerzeichen = O (n) Bits auf einem RAM gelöst werden.) Ist das die Form Ihres Problems?

Sie scheinen vorzuschlagen, dass Sie die Anzahl der Ausgaben verwenden, um eine größere Untergrenze zu erhalten. Sie können jedoch auch damit jede Funktion mit den Eingabebits height = # und space = # berechnen. (Lesen und merken Sie sich die Eingabe und geben Sie alle erforderlichen Werte an jedem Blattknoten aus. Es ist üblich, mehrere Ausgaben an einem einzelnen Knoten zuzulassen.)

Paul Beame
quelle
Vielleicht ist es besser für den Autor, diese Antwort mit der vorherigen zusammenzuführen, da sie fast identisch sind.
Oleksandr Bondarenko