Нижняя граница сложности: разрыв между деревьями решений и ОЗУ

Недавно я обнаружил квадратичную нижнюю границу сложности задачи в модели дерева решений, и мне интересно, можно ли частично обобщить этот результат в модели машины с произвольным доступом. Под частичностью я подразумеваю обобщение программ ОЗУ с определенным временным / пространственным компромиссом. Например, я хотел бы показать, что моя проблема не может быть решена с помощью программы линейного времени и пространства ОЗУ.

А. М. Бен-Амрам и З. Галиль доказали в этой статье, что программа ОЗУ, работающая во времени и пространстве может быть смоделирована за время на машине указателя. Известны ли нам похожие результаты, которые можно применить к деревьям решений?$t$$s$$O(t \, \log s)$

В качестве альтернативы, можно ли имитировать программу ОЗУ, работающую в пространстве с помощью дерева решений степени ? (Интуитивно, косвенная адресация может быть смоделирована с использованием узлов степени )$s$$s$$\leq s$

Естественной моделью, связанной с деревьями решений, которая может имитировать ОЗУ, является программа ветвления. По сути, это дерево решений с общими поддеревьями, объединенными в DAG. Время T и пространство S в ОЗУ можно смоделировать по высоте T и размеру 2 ^ S в программе ветвления. (Возможно, вам придется использовать многоходовое ветвление.)

Для решения проблем ясно, что для любого дерева решений нужны только высота = # входы и пространство = общее количество бит на входе. Обратите внимание, что при многоходовом ветвлении можно иметь # битов на входе больше, чем обычная мера # входов (например, n указателей, каждый из которых принимает log n битов). Для таких проблем с nlog n полными входными битами можно доказать, что некоторые проблемы не могут быть решены за время O (n) и пробел = O (n) бит. Это форма вашей проблемы?

Похоже, вы предлагаете использовать количество выходов, чтобы попытаться получить большую нижнюю границу. Для задач с несколькими выходами обычно разрешается много выходов по одному ребру, а не по конечным узлам (см., Например, статью Бородина-Кука 1982 года о сортировке нижних границ). Однако даже без этого предположения можно также вычислить любую функцию с битами высоты = # input и space = # input. (Прочитайте и запомните входные данные и выведите все значения на каждом листовом узле.)

Естественной моделью, связанной с деревьями решений, которая моделирует ОЗУ без потерь, является программа ветвления. По сути, это дерево решений с общими поддеревьями, объединенными в DAG. Время T и пространство S в ОЗУ можно смоделировать по высоте T и размеру 2 ^ S в программе ветвления. (Возможно, вам придется использовать многоходовое ветвление.)

Для решения проблем ясно, что для любого дерева решений нужны только высота = # входы и пространство = общее количество бит на входе. Обратите внимание, что при многоходовом ветвлении можно иметь # битов на входе больше, чем обычная мера # входов (например, n указателей, каждый из которых принимает log n битов). Для таких проблем с nlog n полными входными битами можно доказать, что некоторые проблемы не могут быть решены за время O (n) и пробел = O (n) битов в ОЗУ.) Это форма вашей проблемы?

Похоже, вы предлагаете использовать количество выходов, чтобы попытаться получить большую нижнюю границу. Однако даже с этим вы также можете вычислить любую функцию с помощью высоты = # входных данных и пробела = # входных битов. (Прочитайте и запомните входные данные и выведите все значения, требуемые на каждом листовом узле. Обычно допускается несколько выходов на одном узле.)