Claramente, não há problemas indecidíveis no NP. No entanto, de acordo com a Wikipedia : NP é o conjunto de todos os problemas de decisão para os quais as instâncias em que a resposta é "sim" têm [..] provas que são verificáveis em tempo polinomial por uma máquina determinística de Turing....
Estou usando um solucionador SAT para codificar um problema e, como parte da instância SAT, tenho variáveis booleanas onde se pretende que exatamente uma delas seja verdadeira e o restante seja falso . (Às vezes, isso é descrito como uma codificação
Estou procurando um algoritmo para distribuir valores de uma lista para que a lista resultante seja o mais "equilibrada" ou "distribuída uniformemente" quanto possível (entre aspas, porque não tenho certeza de que essas são as melhores maneiras de descrevê-la ... mais tarde, fornecerei uma maneira...
Estou interessado na questão de qual a melhor maneira de ensinar a NP-completude aos cursos de ciência da computação. Em particular, devemos ensiná-lo usando reduções de Karp ou reduções de Turing? Sinto que os conceitos de completude e redução de NP são algo que todo especialista em ciência da...
Se alguém construísse um computador quântico universal, isso teria alguma implicação no problema de P vs.
Estou procurando uma estrutura de dados que suporte pesquisas aproximadas eficientes de chaves (por exemplo, distância de Levenshtein para seqüências de caracteres), retornando a correspondência mais próxima possível da chave de entrada. A estrutura de dados mais adequada que eu encontrei até agora...
Você tem uma moeda. Você pode girá-lo quantas vezes quiser. Você deseja gerar um número aleatório tal que onde .a ≤ r < b r , a , b ∈ Z +rrra≤r<ba≤r<ba \leq r < br,a,b∈Z+r,a,b∈Z+r,a,b\in \mathbb{Z}^+ A distribuição dos números deve ser uniforme. É fácil se :b−a=2nb−a=2nb -a = 2^n r =...
Se o problema dos dois generais é insolúvel, como podemos concordar com os seres humanos? Quero dizer, nos comunicamos todos os dias e temos as mesmas limitações que qualquer problema de comunicação tratado pela ciência da computação. Por que isso não nos
Meu problema é como posso provar que uma gramática é inequívoca? Eu tenho a seguinte gramática: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression...
Encontrei várias ferramentas de programação visual de código aberto, como Blockly e amigos, e outros projetos hospedados no Github, mas não consegui encontrar nenhum que funcione diretamente com a árvore de sintaxe abstrata. Por que é que? Estou perguntando porque, uma vez que eu descobri que...
Procurei na net uma resposta para essa pergunta e parece que todo mundo sabe implicitamente a resposta, exceto eu. Presumivelmente, isso ocorre porque as únicas pessoas que se importam são aquelas que tiveram educação superior sobre o assunto. Eu, por outro lado, fui jogado no fundo do poço por um...
Aqui está uma pergunta de um exame passado que estou tentando resolver: Para um gráfico não direcionado com pesos positivos , estou tentando encontrar o corte mínimo. Não conheço outras maneiras de fazer isso além de usar o teorema de min-cut de fluxo máximo. Mas o gráfico não é direcionado, então...
Um filtro Bloom permite controlar com eficiência se vários valores já foram encontrados durante o processamento. Quando existem muitos itens de dados, um filtro Bloom pode resultar em uma economia significativa de memória em uma tabela de hash. O principal recurso de um filtro Bloom, que ele...
Existe uma referência clara, com pseudo-código, sobre como implementar um intérprete Prolog em uma linguagem puramente funcional? O que encontrei até agora parece lidar apenas com linguagens imperativas, é apenas uma demonstração do Prolog implementado por si só, ou não oferece nenhum algoritmo...
Aqui está uma conjectura para expressões regulares: Para a expressão regular , deixe o comprimento | R | seja o número de símbolos nele, ignorando parênteses e operadores. Por exemplo | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2RRR| R ||R||R|| 0∪1 | = | (0∪1 )∗| =2|0∪1|=|(0∪1)∗|=2|0 \cup 1| = |(0 \cup 1)^*|...
Supondo que P NP, os problemas completos de NP sejam "difíceis de resolver, mas têm respostas fáceis de verificar". Faz algum sentido considerar o contrário, ou seja, problemas para os quais é fácil calcular uma resposta correta, mas difícil de verificar uma solução arbitrária?≠≠\neq Eu acho que...
Gostaria de saber se existem experimentos que mostrem a existência ou a inexistência de uma correlação entre o uso de uma linguagem dinâmica (como Python, Ruby ou mesmo linguagens executadas na plataforma Java, como Groovy, Clojure) em um linguagem estática (como C / C ++) e a diferença na...
Não entendo bem por que a rotação na estrutura de dados da árvore de splay está levando em consideração não apenas o pai do nó de classificação, mas também o avô (operação em zig-zag e zig-zig). Por que o seguinte não funcionaria: À medida que inserimos, por exemplo, um novo nó na árvore,...
Um dos hiperparâmetros para redes LSTM é a temperatura. O que é
Qual é a melhor maneira que qualquer um pode fazer para ter uma boa introdução à teoria do sistema distribuído, a livros ou referências e a tópicos e tópicos devem ser abordados primeiro e os requisitos para começar a aprender neste