Ciência da Computação Teórica space-time-tradeoff
Perguntas com a marcação «space-time-tradeoff»
É sabido que os palíndromos podem ser reconhecidos em tempo linear em máquinas de Turing de fitas, mas não em máquinas de Turing de fita única (nesse caso, o tempo necessário é quadrático). O algoritmo de tempo linear usa uma cópia da entrada e, portanto, também usa um espaço linear.222 …
20 cc.complexity-theory time-complexity space-complexity space-time-tradeoff
É fácil ver que qualquer problema decidível no espaço de registro determinístico ( ) é executado no máximo no tempo polinomial ( P ). Muitos algoritmos de espaço de log conhecidos (por exemplo: conectividade st não direcionada, isomorfismo de gráfico plano) são executados em O ( n k ), onde …
17 cc.complexity-theory space-bounded space-time-tradeoff
Precisa de uma boa visão geral dos algoritmos sucintos de estrutura de dados
(já solicitado no site principal , mas solicitando aqui também uma melhor cobertura, desculpe) Desde que eu soube sobre estruturas de dados sucintas, estou precisando desesperadamente de uma boa visão geral dos desenvolvimentos mais recentes nessa área. Pesquisei no Google e li muitos artigos que pude ver no topo dos …
14 reference-request ds.data-structures advice-request space-time-tradeoff
Antecedentes históricos de certos resultados nas compensações espaço-temporais?
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) …
14 cc.complexity-theory ho.history-overview space-time-tradeoff
Troca espaço-tempo e o melhor algoritmo
Considere alguma linguagem tal que:LLL L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) e para que L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) Em outras palavras, a máquina mais rápida calcula L no tempo O ( f ( n ) ) e a máquina mais eficiente em espaço M ' calcula L enquanto usa o …
14 cc.complexity-theory ds.algorithms open-problem space-time-tradeoff
Limites inferiores da troca espaço-tempo
Após a discussão sobre limites mais baixos para o 3SAT [ 1 ], estou pensando quais são os principais resultados de limites inferiores formulados como trocas no espaço-tempo. Estou excluindo resultados como, por exemplo, o teorema de Savitch; uma boa entrada focaria em um único problema e seus limites. Um …
13 cc.complexity-theory ds.algorithms big-list space-time-tradeoff
Computando um oráculo de existência transitiva de conclusão / caminho
Houve algumas perguntas ( 1 , 2 , 3 ) sobre a conclusão transitiva aqui que me fizeram pensar se algo como isso é possível: Suponha que obtemos um gráfico direcionado para entrada e gostaríamos de responder a perguntas do tipo " ?", Ou seja, perguntando se existe uma aresta …
9 graph-theory graph-algorithms space-time-tradeoff transitive-closure
Armazenando um vetor de bits na memória não inicializada e espaço mínimo
Um truque conhecido para armazenar vetores de bits usando memória não inicializada pode alocar um vetor de bits de tamanho no qual todos os bits são definidos como , alocando bits de memória e inicializando apenas deles. Essa representação suporta a configuração e a desabilitação de qualquer bit em tempo …
8 ds.data-structures space-bounded space-time-tradeoff space-complexity
Hamming peso das potências
Dada inteiros positivos e e , o que é conhecido sobre o espaço eo tempo complexidade de encontrar o peso de Hamming (número de 1s binários) de b e ?bbbeeebebeb^e Se os bits estiverem disponíveis, o número pode ser simplesmente calculado por técnicas padrão e os 1s contados. Mas que …