Limite inferior da complexidade: a diferença entre árvores de decisão e RAMs

Recentemente, descobri um limite quadrático inferior à complexidade de um problema no modelo de árvore de decisão e me pergunto se esse resultado pode ser parcialmente generalizado no modelo de máquina de acesso aleatório. Em parte , quero dizer uma generalização para programas de RAM com uma certa troca de tempo / espaço. Por exemplo, eu gostaria de mostrar que meu problema não pode ser resolvido por um programa de RAM com espaço e tempo linear.

AM Ben-Amram e Z. Galil provaram neste artigo que um programa de RAM rodando no tempo espaço pode ser simulado no tempo em uma máquina apontadora. Conhecemos resultados semelhantes que podem ser aplicados às árvores de decisão?$t$$s$$O(t \, \log s)$

Como alternativa, é possível simular um programa de RAM executando no espaço com uma árvore de decisão de graus ? (intuitivamente, o endereçamento indireto pode ser simulado usando nós de grau )$s$$s$$\leq s$

O modelo natural relacionado às árvores de decisão que podem simular RAMs é o programa de ramificação. Basicamente, é uma árvore de decisão com subárvores comuns coalescentes produzindo um DAG. O tempo T e o espaço S em uma RAM podem ser simulados na altura T e tamanho 2 ^ S em um programa de ramificação. (Pode ser necessário usar a ramificação de várias vias.)

Para problemas de decisão, é claro que qualquer árvore de decisão precisa apenas de altura = # entradas e espaço = número total de bits na entrada. Observe que, com a ramificação de várias vias, pode-se ter os # bits na entrada maiores que a medida usual do # de entradas (por exemplo, n ponteiros cada um recebendo log n bits). Para esses problemas com nlog n bits totais de entrada, pode-se provar que certos problemas não podem ser resolvidos no tempo O (n) e space = O (n) bits. Essa é a forma do seu problema?

Você parece sugerir que está usando o número de saídas para tentar obter um limite inferior maior. É comum que problemas com várias saídas permitam muitas saídas ao longo de uma única borda em vez de nos nós das folhas (consulte, por exemplo, o artigo de Borodin-Cook de 1982 sobre a classificação dos limites inferiores). No entanto, mesmo sem essa suposição, também é possível calcular qualquer função com altura = # entradas e espaço = # bits de entrada. (Leia e lembre-se da entrada e produza todos os valores em cada nó da folha.)

O modelo natural relacionado às árvores de decisão que simula RAMs sem perda é o programa de ramificação. Basicamente, é uma árvore de decisão com subárvores comuns coalescentes produzindo um DAG. O tempo T e o espaço S em uma RAM podem ser simulados na altura T e tamanho 2 ^ S em um programa de ramificação. (Pode ser necessário usar a ramificação de várias vias.)

Para problemas de decisão, é claro que qualquer árvore de decisão precisa apenas de altura = # entradas e espaço = número total de bits na entrada. Observe que, com a ramificação de várias vias, pode-se ter os # bits na entrada maiores que a medida usual do # de entradas (por exemplo, n ponteiros cada um recebendo log n bits). Para esses problemas com nlog n bits totais de entrada, pode-se provar que certos problemas não podem ser resolvidos no tempo O (n) e space = O (n) bits em uma RAM.) Essa é a forma do seu problema?

Você parece sugerir que está usando o número de saídas para tentar obter um limite inferior maior. No entanto, mesmo com isso, você também pode calcular qualquer função com altura = # entradas e espaço = # bits de entrada. (Leia e lembre-se da entrada e faça a saída de todos os valores necessários em cada nó folha. É comum permitir várias saídas em um único nó.)