Você conhece algum wiki atualizado dedicado a problemas de otimização de NP com seus melhores resultados de aproximação e dureza? Com base no feedback, parece seguro presumir que não exista esse recurso (consulte o final desta pergunta para duas opções próximas). - adicionado em 8 de...
Quais seriam as consequências de #P = FP? Estou interessado em conseqüências práticas e teóricas. Do ponto de vista prático, estou particularmente interessado em consequências na inteligência artificial. Ponteiros para papéis ou livros são mais que bem-vindos. Por favor, não diga que #P = FP...
Dado um idioma comum (NFA, DFA, gramática ou regex), como pode ser contado o número de palavras aceitantes em um determinado idioma? Tanto "com exatamente n letras" quanto "com no máximo n letras" são de interesse. Margareta Ackerman tem dois trabalhos sobre o assunto relacionado de enumerar...
Eu não sou um teórico da ciência da computação, mas acho que esse problema do mundo real pertence aqui. O problema Minha empresa possui várias unidades em todo o país. Oferecemos aos funcionários a possibilidade de trabalhar em outra unidade. Mas há uma condição: o número total de trabalhadores...
Formulei o seguinte problema hoje, enquanto brincava com o meu GPS. Aqui está : Seja um gráfico direcionado, de modo que se então , ou seja, é uma orientação do gráfico não direcionado subjacente. Considere as seguintes operações:G(V,E)G(V,E)G(V,E)e=(u,v)∈Ee=(u,v)∈Ee=(u,v) \in E(v,u)∉E(v,u)∉E(v,u)...
Volume III de Knuth de The Art of Computer Programming (capítulo 5, versículo 3.2) inclui o seguinte tabela listando o exato número mínimo de comparações necessárias para selecionar o th menor elemento de um conjunto indiferenciado de tamanho , para todos . Esta tabela, juntamente com as conhecidas...
Preciso calcular a mediana em execução: Entrada: nnn , kkk , vetor .( x1, x2, … , Xn)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Saída: vetor , em que é a mediana de .y i ( x i , x i + 1 , … , x i + k - 1 )( y1, y2, … , Yn - k + 1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1})yEuyiy_i( xEu, xi + 1, … , Xi...
O que se sabe sobre a complexidade do seguinte problema: Dado: números racionais x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n . Saída: números inteiros y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n . Objetivo: minimizar ∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1 \le i < j...
Geralmente, constrói-se um gráfico e, em seguida, faz-se perguntas sobre a decomposição do autovalor da matriz de adjacência (ou algum parente próximo como o Laplaciano ) (também chamado de espectro de um gráfico ). Mas e o problema inverso? Dados valores próprios, é possível (eficientemente)...
Os solucionadores SAT são muito importantes em ataques algébricos , por exemplo, walkinsat e minisat . No entanto, ao resolver os problemas de benchmark disponíveis aqui, há uma enorme diferença de desempenho entre os dois - o Walksat é muito mais rápido que o minisat para esses problemas. Por que...
Em conexão com a Slither Fazer a ligação quebra-cabeça, eu estive pensando: Suponha que eu tenho um grade de células quadrados, e eu quero encontrar um ciclo simples de bordas de grade, uniformemente de forma aleatória entre todos os ciclos simples possíveis.n×nn×nn\times n Uma maneira de fazer...
Dados nnn subconjuntos S1,…,SnS1,…,SnS_1,\ldots,S_n de {1,…,d}{1,…,d}\{1,\ldots,d\} . Si,SjSi,SjS_i,S_jSi⊊SjSi⊊SjS_i \subsetneq S_j A solução trivial para esse problema passa por todos os pares de conjuntos e verifica a inclusão de um par no tempo , portanto, o tempo de execução geral é . Esse...
Existe um análogo paralelo natural às árvores de vermelho-preto com propriedades semelhantes ou até mesmo terrivelmente piores para atualizações, sendo razoavelmente eficiente no trabalho? De um modo mais geral, o que podemos fazer de melhor para pesquisas paralelas com atualizações?...
Um gráfico H é um núcleo se qualquer homomorfismo de H para si é uma bijeção. Um subgrafo H de G é um núcleo de G se H é um núcleo e existe um homomorfismo de G para H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29 Dado um gráfico G, qual é o algoritmo exato mais conhecido para encontrar...
O algoritmo de Coppersmith – Winograd é o algoritmo conhecido mais rapidamente assintoticamente para multiplicar duas matrizes quadradas. O tempo de execução de seu algoritmo é o mais conhecido até o momento. Qual é a complexidade espacial deste algoritmo? Está em ?O ( n 2.376 ) Θ ( n 2 )n × nn×nn...
Edit: Eu primeiro formulei minha restrição (2), agora ela está corrigida. Eu também adicionei mais informações e exemplos. Com alguns colegas, estudando outra questão algorítmica, conseguimos reduzir nosso problema ao seguinte problema interessante, mas não conseguimos resolver a questão de sua...
Problema no casamento estável: http://en.wikipedia.org/wiki/Stable_marriage_problem Estou ciente de que, para uma instância de um SMP, muitos outros casamentos estáveis são possíveis além daquele retornado pelo algoritmo Gale-Shapley. No entanto, se recebermos apenas , o número de homens /...
Eu quero fazer um primeiro solucionador de SAT. Conheço a competição do SAT e a conferência do SAT, e há tantos artigos sobre esse assunto. Eu sou um iniciante, um iniciante oprimido. Por onde devo começar? Eventualmente, eu quero empurrar o estado da arte. Quero alguns conselhos de especialistas...
Dado um enorme banco de dados de palavras permitidas (classificadas em ordem alfabética) e uma palavra, encontre a palavra no banco de dados mais próxima da palavra especificada em termos de distância de Levenshtein. A abordagem ingênua é, é claro, simplesmente calcular a distância de levenshtein...
A largura da árvore mede a distância entre um gráfico e uma árvore. É NP-difícil calcular a largura da árvore. O algoritmo de aproximação mais conhecido atinge fator.O(logn−−−−√)O(logn)O(\sqrt{{\log}n}) O teorema de Courcelle afirma que qualquer propriedade dos gráficos definíveis na lógica...