( ATUALIZAÇÃO : uma pergunta melhor formada é colocada aqui, pois os comentários para a resposta aceita abaixo mostram que essa pergunta não está bem definida) A prova clássica da impossibilidade do problema de parada depende de demonstrar uma contradição ao tentar aplicar o algoritmo de...
Uma função f: { 0 , 1 }∗→ { 0 , 1 }∗f:{0 0,1 1}∗→{0 0,1 1}∗f \colon \{0, 1\}^* \to \{0, 1\}^* é unidirecional se fff puder ser calculada por um algoritmo de tempo polinomial, mas para cada algoritmo de tempo polinomial aleatório UMAUMAA , Pr [ f( A ( f( x ) ) ) = f( x ) ] < 1 / p ( n...
Dado um conjunto S de nxn matrizes de permutação (que é apenas uma pequena fração das n! Possíveis matrizes de permutação), como podemos encontrar subconjuntos de tamanho mínimo T de S de modo que a adição de matrizes de T tenha pelo menos 1 em todas as posições? Estou interessado neste problema...
Esta é uma pergunta no espírito desta, em que respondi que é importante acompanhar o que você fez alguma coisa, por que você fez e o que não está funcionando. Pessoalmente, uso notebooks para esse fim, mas há várias desvantagens: primeiro, preciso de muita superfície de armazenamento; segundo,...
Recebemos uma família de m subconjuntos de {1, ..., n}. É possível encontrar um limite inferior não trivial à complexidade de decidir se F é uma família Sperner? O limite inferior trivial é O ( n m ) e eu suspeito fortemente que ele não seja rígido.FF\mathcal{F}mmmFF\mathcal{F}O ( n m )O(nm)O(n...
Dados os pontos em e uma distância encontro o maior subconjunto desses pontos, de modo que a distância euclidiana de nenhum deles exceda .p1,…,pnp1,…,pnp_1,\ldots,p_nRdRd\mathbb{R}^{d}llllll Qual é a complexidade desse problema? No gráfico sobre os pontos que têm uma aresta sempre que a distância...
Uma pergunta recente discutiu o agora clássico algoritmo de programação dinâmica para TSP, devido independentemente a Bellman e Held-Karp . O algoritmo é universalmente relatado para ser executado no tempo O ( 2nn2)O(2nn2)O(2^n n^2) . No entanto, como um dos meus alunos apontou recentemente, esse...
Dadas duas árvores AVL e T 2 e um valor t r tal que ∀ x ∈ T 1 , ∀ y ∈ T 2 , x < t r < y , é fácil de construir uma nova árvore AVL contendo t r e os valores em T 1 e T 2 , em tempo O ( 1 + | h ( T 1 ) - H ( TT1 1T1 1T_1T2T2T_2trtrt_r∀ x ∈ T1 1, ∀ y∈ T2, x < tr< y∀x∈T1...
Seja K(x)K(x)K(x) denotado a complexidade Kolmogorov de uma string . Existe uma cadeia de caracteres tal que . (Aqui é a concatenação de consigo). Uma pergunta semelhante, mas diferente, foi feita aqui , mas o contra-exemplo dado na resposta a essa pergunta não funciona para
supAOPTsupAOPT\sup\frac{A}{OPT}MINMINMINAAAAAAOPTOPTOPTinfΩ−AΩ−OPTinfΩ−AΩ−OPT\inf\frac{\Omega-A}{\Omega-OPT}ΩΩ\Omega fornece a mesma taxa de aproximação para problemas como cobertura mínima de vértices e conjunto independente máximo, que são conhecidos por serem apenas realizações diferentes do...
É sabido que as fórmulas aleatórias de CNF sobre n variáveis com cláusulas c n são insatisfatórias (isto é, são contradições) com alta probabilidade, para uma constante suficientemente grande c . Assim, as fórmulas aleatórias de k- CNF (para c suficientemente grandes) constituem uma distribuição...
Depois de trabalhar com 2-3 árvores de dedos, fiquei impressionado com a velocidade deles na maioria das operações. No entanto, o único problema que encontrei é a grande sobrecarga associada à criação inicial de uma grande árvore de dedos. Como a construção é definida como uma sequência de...
Fiquei me perguntando se existe uma boa bibliografia de tentativas de investigar a conjectura de Collatz como uma gramática formal. (ou quaisquer outras tentativas na comunidade de CS para lidar com essa classe de fenômenos generativos e suas propriedades de
Existe alguma teoria da linguagem de programação descrevendo interfaces de função estrangeira (FFI) e várias ligações de linguagem? Eu perguntei alguns problemas de implementação no stackoverflow , o que não é adequado aqui. Mas gostaria de perguntar a partir da visualização deste site e ver o...
Uma das coisas surpreendentes da ciência da computação é que a implementação física é, em certo sentido, "irrelevante". As pessoas construíram computadores com sucesso em vários substratos diferentes - relés, tubos de vácuo, transistores discretos etc. Em breve, as pessoas poderão construir...
O caso de gráficos fortemente regulares é o mais difícil para testes de IG? onde "mais difícil" é usado em algum significado de "senso comum" ou "em média", por assim dizer. Wolfram MathWorld menciona alguns "gráficos patologicamente difíceis". O que eles são? Meu conjunto de amostra de 25...
Faça um gráfico direcionado onde as bordas são decoradas com um número natural. Queremos o conjunto de todos os caminhos P entre dois vértices v 1 e v 2, de modo que cada aresta sucessiva no caminho seja decorada com um número natural que seja maior que o número natural que decora a aresta...
Muitas vezes queremos definir um objeto acordo com algumas regras de inferência. Estas regras denotar uma função de geração de que, quando ele é monótona, produz um ponto fixo menos . Tomamos para ser a "definição indutiva" de . Além disso, a monotonicidade de nos permite argumentar com o...
O que devo ler para entender esse problema? O poder dos circuitos quânticos de pequena profundidade. Is ? Em outras palavras, a parte "quântica" de qualquer algoritmo quântico pode ser compactada até a profundidade do polilog (n), desde que desejemos realizar um pós-processamento clássico em...
O manuscrito a seguir está disponível publicamente? Dana Scott, 1969, uma teoria das funções computáveis do tipo superior . Notas não publicadas do seminário, 7 páginas, University of Oxford. Há uma discussão deste artigo na seção 8.1.2, Tipos como conjuntos , em Cardone & Hindley, 2006...