Estou procurando uma referência para o seguinte resultado: Adicionar dois números inteiros na representação fatorada é tão difícil quanto fatorar dois números inteiros na representação binária usual. (Tenho certeza de que está lá fora, porque isso é algo que eu já tinha pensado em algum...
Acabei de perceber que estou assumindo que a resposta para minha pergunta é "sim", mas não tenho um bom motivo. Imagino que talvez exista um coletor de lixo que, provavelmente, introduza apenas a desaceleração do pior dos casos . Existe uma referência definitiva que posso citar? No meu caso, estou...
No artigo "A COMPLEXIDADE DOS PROBLEMAS DE SATISFIABILIDADE", de Thomas J. Schaefer, o autor mencionou que This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the...
Esta pergunta é sobre a complexidade do tempo do algoritmo de fluxo máximo de Ford-Fulkerson ao usar o DFS para encontrar caminhos de aumento. Há um exemplo conhecido que mostra que o uso do DFS pode precisar de um número linear de iterações no fluxo máximo; veja, por exemplo, a página da...
Alguém sabe de referências que explicitam precisamente a conexão entre o algoritmo de unificação e a eliminação gaussiana? Estou particularmente interessado na relação entre substituições triangulares e decomposições de LU. Wayne Snyder e Jean Gallier mencionam essa analogia de passagem em seu...
Ao mexer na análise de LR não-canônica, pensei em um método de análise (com tabelas de tamanho infinito, o que o torna um tanto impraticável ) capaz de analisar exatamente as gramáticas inequívocas no tempo , e me perguntei se é possível fazer melhor. :O ( n2)O(n2)O(n^2) Todas as gramáticas...
Ao projetar algoritmos de aproximação, às vezes se resolve um programa semidefinido seguido de uma etapa de arredondamento. Um exemplo frequentemente usado para ilustrar isso é o Max-Cut. (Veja, por exemplo, Algoritmos de Aproximação de Vijay Vazirani.) Existem boas fontes educacionais ou...
Seja um gráfico. Para um vértice x ∈ V , definir N ( x ) para ser o (aberto) vizinhança de x em L . Ou seja, N ( x ) = { y ∈ VG = ( V, E)G=(V,E)G=(V,E)x ∈ Vx∈Vx\in VN( X )N(x)N(x)xxxGGG . Defina dois vértices u , v em G comogêmeosse u e v tiverem o mesmo conjunto de vizinhos, ou seja, se N ( u ) =...
Existe uma boa pesquisa que compara diferentes extratores, concentradores e superconcentradores e estabeleça os melhores métodos em termos de troca entre aleatoriedade, tempo e espaço?
Encontrei o seguinte resultado durante minha pesquisa. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 onde m=ω(n−−√)m=ω(n)m=\omega(\sqrt n) e a1,⋯,ama1,⋯,ama_1,\cdots,a_m são...
Existem muitos lugares onde os números e aparecem. Estou curioso para saber sobre algoritmos cujo tempo de execução contém a proporção áurea ou no
Antecedentes: Deixe- ser dois vértices de um grafo não direcionado G = ( V , E ) . Um conjunto vértice S ⊆ V é um u , v -separator se u e v pertencem a diferentes componentes ligados de L - S . Se nenhum subconjunto adequado de um u , v -separator S for u , v -separator, então S será um mínimo u...
(Este é um acompanhamento para esta pergunta e sua resposta .) Eu tenho o seguinte programa linear inteiro totalmente unimodular (TU) (ILP). Aqui ℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,wℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,w\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w são números inteiros positivos dados...
captura a idéia de eficientemente paralelizável, e uma interpretação disso são problemas que são solucionáveis no tempo O ( log c n ) usandoprocessadores paralelos O ( n k ) para algumas constantes c , k . Minha pergunta é se existe uma classe de complexidade análoga em que o tempo é n c e o...
Estou procurando idiomas que "provavelmente não são livres de contexto", mas não podemos (des) provar isso usando técnicas padrão conhecidas. Existe uma pesquisa recente sobre o assunto ou uma seção de problemas abertos de uma conferência recente? Provavelmente, não existem muitos idiomas...
Eu já vi (e ouvi) afirmar que é seguro acrescentar o axioma clássico do meio excluído ao Coq, mas não consigo encontrar um documento que apoie essa afirmação. Os artigos que vejo listados no wiki da Coq sobre o meio excluído estão mostrando inconsistência com o conjunto impredicativo. De fato,...
Quando ensino limites de cauda, uso a progressão usual: Se seu rv for positivo, você pode aplicar a desigualdade de Markov Se você tiver independência e também variância limitada, poderá aplicar a desigualdade de Chebyshev Se cada rv independente também tiver todos os momentos limitados, você...
Considere o seguinte raciocínio: Seja denotado a complexidade de Kolmogorov da cadeia . O teorema da incompletude de Chaitin diz queK( X )K(x)K(x)xxx para qualquer sistema formal consistente e suficientemente forte , existe uma constante (dependendo apenas do sistema formal e sua linguagem) de...
Recentemente, trabalhei no problema para calcular a soma aproximada de uma lista de números não negativos classificados. Para qualquer fixo ϵ>0ϵ>0\epsilon>0 , um Esquema do tempo de aproximação foi derivado de modo a que ele dá uma -approximation para a soma. O artigo está publicado em...
Uma cadeia de adição é uma sequência de números inteiros positivos que e cada índice , temos para alguns índices . O comprimento da cadeia de adição é ; o alvo da cadeia de adição é .x 1 = 1 i ≥ 2 x i = x j + x k 1 ≤ j , k < i( x1, x2, … , Xn)(x1,x2,…,xn)(x_1, x_2, \dots, x_n)x1= 1x1=1x_1 = 1i ≥...