Em termos de pior tempo de execução assintótico, qual problema de NP-completo possui o algoritmo mais rápido (exato) conhecido e qual é o algoritmo? Existe algo conhecido que é mais rápido que O(n2∗2n)O(n2∗2n)O(n^2*2^n)
Eu tenho uma pergunta muito genérica a fazer. Está relacionado à pesquisa. Estou interessado na teoria dos grafos. Eu fiz um curso nele. Fiz alguns tópicos relacionados à teoria dos grafos como ponto de vista de fazê-lo como estudante de matemática e também estudei alguns algoritmos de grafos. Vou...
Perdoe a ingenuidade que será óbvia na maneira como faço essa pergunta, bem como no fato de estar fazendo. Os matemáticos normalmente usam , pois é a base mais simples / mais agradável da teoria (devido ao cálculo). Mas os computadores parecem fazer tudo em binário, então é mais rápido em uma...
Há muitos detalhes sobre os carregadores de carregadores de olhais, como Kogge-Stone, Lander-Fischer, etc. nos cursos de CS da faculdade. Eles são descritos como "comuns no setor". No entanto, não consigo encontrar nenhuma evidência (além da cadeia de transporte de Manchester) nos últimos tempos,...
Eu me deparei com essa pergunta: "Dê exemplos de dois idiomas regulares em que a união deles não produz um idioma comum". Isso é muito chocante para mim, porque acredito que os idiomas regulares são fechados sob união. Que significa para mim que se eu tomar duas linguagens regulares e união...
Eu sei que isso pode parecer um pouco fora da caixa, na verdade eu costumava pensar sempre dentro da caixa, mas recentemente eu tenho pensado, possivelmente porque a ciência da computação oferece um alto grau de liberdade, sobre maneiras de conceber programas diferentes de os ensinados na...
Adoro tudo o que é tempo de compilação e adoro a idéia de que, depois que você compila um programa, muitas garantias são feitas sobre sua execução. De um modo geral, um sistema de tipo estático (Haskell, C ++, ...) parece oferecer garantias mais fortes em tempo de compilação do que qualquer sistema...
Eu fiz um pouco de pesquisa no google e fiquei um pouco curto. Gostaria de saber quais são as principais razões para os cientistas da computação, programadores, estudarem a reescrita de termos e / ou a reescrita de gráficos de termos. Até onde eu sei, isso apenas ajuda no raciocínio básico sobre...
Ao ler alguns blogs sobre complexidade computacional (por exemplo, aqui ), eu assimilei a noção de que decidir se dois grupos são isomórficos é mais fácil do que testar dois gráficos quanto ao isomorfismo. Por exemplo, na página declarada, diz que o isomorfismo do gráfico é um problema mais geral...
Na foto abaixo, estou tentando descobrir o que exatamente esse NFA está aceitando. O que me confunde é o salto em .ϵϵ\epsilonq0q0q_0 Se um for inserido, o sistema passa para e (o estado de aceitação)?000q0q0q_0 q1q1q_1 Se um for inserido, o sistema passa para e ?111q1q1q_1q2q2q_2 O sistema...
As tabelas de hash perfeitas dinâmicas e as tabelas de hash do cuco são duas estruturas de dados diferentes que suportam pesquisas de pior caso O (1) e inserções e exclusões esperadas em tempo de O (1). Ambos requerem O (n) espaço auxiliar e acesso a famílias de funções de hash para suas...
Tenho problemas para entender o problema de parada de Turing. Sua prova supõe que exista uma máquina mágica que possa determinar se um computador interromperá ou repetirá para sempre uma determinada entrada. Em seguida, anexamos outra máquina que inverte a saída e temos uma contradição e,...
O objetivo é criar o DFA a partir de uma expressão regular e o uso de "Exp regular> NFA> conversão do DFA" não é uma opção. Como alguém deveria fazer isso? Fiz essa pergunta ao nosso professor, mas ele me disse que podemos usar a intuição e se recusou a fornecer qualquer explicação. Então,...
Vi como o XOR-3-SAT é eficientemente solucionável (por exemplo, consulte a seção "XOR-satisfability" na entrada da Wikipedia para o problema de satisfação booleana ). Estou pensando em uma pergunta básica: O XOR-k-SAT é eficientemente solucionável, para fórmulas com quantidades variáveis de...
Existe um problema popular [1] [2] na ciência da computação que está encontrando um número mínimo de linhas retas que cobre um determinado conjunto de pontos em 2D. Embora tenha digitalizado muitos papéis, nenhum deles tem uma clara motivação para o problema. Qual é a utilidade de resolver esse...
Esta é provavelmente uma pergunta estúpida, mas eu simplesmente não entendo. Em outra questão, eles apresentaram o teorema da dicotomia de Schaefer . Para mim, parece que prova que todo problema de CSP está em P ou em NP-complete, mas não no meio. Como todo problema de NP pode ser transformado no...
Estou curioso para saber se há algum problema completo na classe de complexidade Arthur-Merlin. Gráfico O não-isomorfismo (RNB) parece ser o exemplo canônico de um problema no AM, mas provavelmente não é completo. Suponho que também esteja pensando se um problema "completo" está bem definido para...
Estou projetando um banco de dados de objetos na memória para um caso de uso muito específico. É um escritor único, mas deve suportar leituras simultâneas eficientes. As leituras devem ser isoladas. Não há linguagem de consulta, o banco de dados suporta apenas: obter objetos / s por atributo /...
A distância de edição Levenshtein-Distance entre listas é um problema bem estudado. Mas não consigo encontrar muitas melhorias possíveis, se soubermos que nenhum elemento ocorre mais de uma vez em cada lista . Vamos supor também que os elementos são comparáveis / classificáveis (mas as...
Eu sou novo em autômatos e recebi uma breve introdução às expressões regulares apenas ontem. Eu li as várias regras para definir uma expressão regular. Mas não sou capaz de diferenciar expressões regulares e gramática de um idioma (não aprendi a gramática para expressões regulares). Entendo que a...