Złożoność: granica między drzewami decyzyjnymi a pamięciami RAM

Niedawno odkryłem kwadratową dolną granicę złożoności problemu w modelu drzewa decyzyjnego i zastanawiam się, czy ten wynik można częściowo uogólnić na model maszyny o swobodnym dostępie. Przez częściowo , to znaczy uogólnienie do ubijania programów o określonym czasie / przestrzeni kompromis. Na przykład chciałbym pokazać, że mojego problemu nie można rozwiązać za pomocą programu RAM o czasie liniowym i przestrzeni.

AM Ben-Amram i Z. Galil udowodnili w tym artykule, że program RAM działający w czasie przestrzeni s może być symulowany w O ( $t$$s$ czas na maszynie wskaźnikowej. Czy znamy podobne wyniki, które można zastosować do drzew decyzyjnych?$O(t \, \log s)$

Alternatywnie, czy można symulować program RAM działający w przestrzeni z drzewem decyzyjnym stopni s ? (intuicyjnie adresowanie pośrednie można symulować przy użyciu węzłów stopnia ≤ s )$s$$s$$\leq s$

Naturalnym modelem związanym z drzewami decyzyjnymi, które mogą symulować pamięci RAM, jest program rozgałęziający. Zasadniczo jest to drzewo decyzyjne z połączonymi wspólnymi poddrzewami, dającymi DAG. Czas T i przestrzeń S w pamięci RAM można symulować w wysokości T i rozmiarze 2 ^ S w programie rozgałęziającym. (Może być konieczne użycie rozgałęzienia wielokierunkowego).

W przypadku problemów decyzyjnych jest jasne, że każde drzewo decyzyjne wymaga jedynie wysokości = # danych wejściowych i spacja = całkowita liczba bitów na wejściu. Zauważ, że w przypadku rozgałęzień wielostronnych można mieć # bitów na wejściu większą niż zwykła miara liczby wejść (np. N wskaźników, z których każdy przyjmuje log n bitów.) W przypadku takich problemów z nlog n całkowitymi bitami wejściowymi można udowodnić, że pewnych problemów nie można rozwiązać w czasie O (n) i spacji = O (n) bitach. Czy to jest twoja forma problemu?

Wydaje się, że sugerujesz, że używasz # wyjść, aby spróbować uzyskać większą dolną granicę. Zazwyczaj w przypadku problemów z wieloma wydrukami zezwala się na wiele wydruków wzdłuż jednej krawędzi, a nie w węzłach liści (patrz na przykład artykuł Borodina-Cooka z 1982 r. Na temat sortowania dolnych granic). Jednak nawet bez tego założenia można również obliczyć dowolną funkcję przy użyciu wysokości = liczba wejść i spacja = liczba bitów wejściowych. (Przeczytaj i zapamiętaj dane wejściowe i wyślij wszystkie wartości w każdym węźle liścia).

Naturalnym modelem związanym z drzewami decyzyjnymi, który symuluje pamięci RAM bez strat, jest program rozgałęziający. Zasadniczo jest to drzewo decyzyjne z połączonymi wspólnymi poddrzewami, dającymi DAG. Czas T i przestrzeń S w pamięci RAM można symulować w wysokości T i rozmiarze 2 ^ S w programie rozgałęziającym. (Może być konieczne użycie rozgałęzienia wielokierunkowego).

W przypadku problemów decyzyjnych jest jasne, że każde drzewo decyzyjne wymaga jedynie wysokości = # danych wejściowych i spacja = całkowita liczba bitów na wejściu. Zauważ, że w przypadku rozgałęzień wielostronnych można mieć # bitów na wejściu większą niż zwykła miara liczby wejść (np. N wskaźników, z których każdy przyjmuje log n bitów.) W przypadku takich problemów z nlog n całkowitymi bitami wejściowymi można udowodnić, że pewnych problemów nie można rozwiązać w czasie O (n) i spacji = O (n) bitów w pamięci RAM.) Czy to jest forma twojego problemu?

Wydaje się, że sugerujesz, że używasz # wyjść, aby spróbować uzyskać większą dolną granicę. Jednak nawet przy tym można również obliczyć dowolną funkcję za pomocą wysokości = # wejść i spacji = # bitów wejściowych. (Przeczytaj i zapamiętaj dane wejściowe i wyślij wszystkie wartości wymagane w każdym węźle liścia. Zwykle zezwala się na wiele wyjść w jednym węźle.)