Antecedentes históricos de certos resultados nas compensações espaço-temporais?

14

Estou interessado no histórico inicial de resultados publicados sobre compensações de espaço-tempo de uso geral. Em particular, quero saber quem primeiro descreveu o seguinte tipo de algoritmo para avaliar uma computação com um gráfico de fluxo de dados arbitrário com grau O (1) usando espaço proporcional à profundidade (não largura) do gráfico de fluxo de dados (mais o tamanho da entrada) fazendo uma avaliação direta e profunda da profundidade do gráfico. Em mais detalhes:

Seja o gráfico do fluxo de dados G = (V, E) onde V é o conjunto de vértices computacionais (valores de dados de tamanho O (1)) e E é o conjunto de arestas (v_p, v_s), de modo que o valor do sucessor o vértice v_s \ in V depende imediatamente do valor do vértice predecessor v_p \ in V. Seja v_f o vértice sem sucessores representando o resultado final da computação. Seja eu um conjunto de vértices de entrada ordenados canonicamente (sem predecessores), pois i \ in I é fornecido seu valor x (i). Para outros vértices v \ in S, seus valores são definidos por x (v) = F_v (x (P (v))) em que P (v) é uma lista canonicamente ordenada dos predecessores de v, x (P (v)) é a lista correspondente de seus valores e F_v é a função do vértice que determina seu valor como uma função da lista de valores de seus predecessores.

Dada essa configuração, o algoritmo em questão é bastante óbvio e trivial:

def eval(v):     (v can be any vertex in the graph)
   let P := P(v), the list of v's predecessors  (has O(1) elements by assumption)
   let val[] := uninitialized array of |P| data values
   for each predecessor p[i] in P (i.e. for i from 1 to |P|):
      if p[i] is in I then
         val[i] = x(p)      (look up a given input)
      else
         val[i] = eval(p[i])   (recursive call)
   return F_v(val[])        (apply vertex's function to list of predecessor values)

Isso leva a O (d) níveis de recursão, onde d é a profundidade do gráfico do fluxo de dados e o espaço da pilha em cada nível é constante devido às suposições de que o grau do gráfico do fluxo de dados é constante e que o tamanho de os valores dos dados são constantes. (Para simplificar aqui, estou tratando o tamanho das referências de vértice também como constantes, mesmo que sejam realmente logarítmicas em | V |.) Assim, o uso total de espaço é O (d + | I |). A largura máxima do gráfico de fluxo de dados pode ser exponencialmente maior que isso; portanto, na melhor das hipóteses, essa técnica pode proporcionar uma economia de espaço bastante extrema, em comparação com, por exemplo, uma avaliação ambiciosa e avançada do gráfico (que pode ser a cada etapa, avalie todos os vértices que dependem diretamente apenas de vértices cujos valores já são conhecidos,

De qualquer forma, é uma técnica bastante óbvia, pelo menos em retrospecto, e certamente é conhecida há muito tempo, mas eu estava me perguntando o quanto a literatura sobre isso vai voltar. Alguém conhece a história inicial de resultados desse tipo (descritos nesses termos ou outros análogos) e qual seria uma boa referência para se aprofundar nesse assunto?

Muito obrigado, -Mike Frank

Michael Frank
fonte

Respostas:

10

Não sei se é a primeira ocorrência ou não, mas a construção aparece na prova do Lema 1 de Borodin [Bor77] sobre a complexidade espacial da avaliação de um circuito booleano. (Ele contém um pouco mais do que apenas a idéia de avaliação recursiva para reduzir a complexidade do espaço, de bits O ( D log S ) para bits O ( D + log S ), onde D é a profundidade do circuito e S é o tamanho de o circuito.)

Allan Borodin. Relacionando tempo e espaço com tamanho e profundidade. SIAM Journal on Computing , 6 (4): 733-744, dezembro de 1977. DOI: 10.1137 / 0206054 .

Tsuyoshi Ito
fonte