O título indica a pergunta. Temos como entradas uma lista de elementos que podemos comparar (determinar qual é o melhor ). Nenhum elemento pode ser igual. Pontos chave: A comparação não é transitiva (pense em uma tesoura de papel de pedra): isso pode ser verdade: A> B, B> C, C> A...
Então eu entendo a ideia de que o problema de decisão é definido como Existe um caminho P tal que o custo seja menor que C? e você pode facilmente verificar se isso é verdade, verificando o caminho que você recebe. No entanto, e se não houver um caminho que atenda a esse critério? Como você...
Quando o código da máquina está realmente sendo executado pelo hardware e pela CPU, como ele é? Seria binário, como nas instruções representadas por uns e zeros, ou seria algo composto por dígitos hexadecimais em que opcodes são bytes apresentados como números hexadecimais que podem ser divididos...
Alfabeto de origem:{ a , b , c , d, e , f}{uma,b,c,d,e,f}\{a, b, c, d, e, f\} Alfabeto do código:{ 0 , 1 }{0 0,1}\{0, 1\} a : 0101uma:0101a\colon 0101 b : 1001b:1001b\colon 1001 c : 10c:10c\colon 10 d: 000d:000d\colon 000 e : 11e:11e\colon 11 f: 100f:100f\colon 100 Eu pensei que, para um...
De acordo com Immerman , a classe de complexidade associada às consultas SQL é exatamente a classe de consultas seguras em (consultas de primeira ordem e operador de contagem): o SQL captura consultas seguras. (Em outras palavras, todas as consultas SQL têm uma complexidade em \ mathsf {Q (FO...
Existem muitas maneiras de definir a Complexidade Kolmogorov e , geralmente, todas essas definições são equivalentes a uma constante aditiva. Isto é, se e são Kolmogorov funções de complexidade (definida através de diferentes línguas ou modelos), então existe uma constante tal que, para cada corda...
Considere os problemas de decisão declarados em uma linguagem formal "razoável". Digamos fórmulas na aritmética Peano de ordem superior com uma variável livre como quadro de referência, mas estou igualmente interessado em outros modelos de computação: equações diofantinas, problemas de palavras ao...
Considere árvores binárias enraizadas e sem rótulo. Nós podemos comprimir essas árvores: sempre que houver indicações de sub-árvores e com (interpretação a igualdade estrutural), armazenamos (WLOG) e substituir todos os ponteiros para com ponteiros para . Veja a resposta de uli para um exemplo.T ′...
O algoritmo GSAT é, em grande parte, direto: você obtém uma fórmula na forma normal conjuntiva e inverte os literais das cláusulas até encontrar uma solução que satisfaça a fórmula ou atingir o limite max_tries / max_flips e não encontra solução. Estou implementando o seguinte...
Desejo analisar idiomas específicos do domínio definido pelo usuário. Essas linguagens são tipicamente próximas de notações matemáticas (não estou analisando uma linguagem natural). Os usuários definem sua DSL em uma notação BNF, assim: expr ::= LiteralInteger | ( expr ) | expr + expr | expr *...
Eu me pergunto se as unidades de computação massivamente paralelas fornecidas nas placas gráficas atualmente (uma que é programável no OpenCL , por exemplo) são boas o suficiente para simular autômatos celulares 1D (ou talvez autômatos celulares 2D?) De maneira eficiente. Se escolhermos qualquer...
Em relação ao portão quântico de Toffoli : é clássico universal, e se sim, por que? é quantumly universal e por
Para criptografar uma mensagem com uma tecla de teclado único faça .m1m1m_1kkkEn c ( m1, k ) = m1⊕ kEnc(m1,k)=m1⊕kEnc(m_1,k) = m_1 \oplus k Se você usar o mesmo para criptografar uma mensagem diferente obtém , e se você executa Xor dos dois textos cifrados, obtém kkkm2m2m_2En c ( m2, k ) = m2⊕...
Não é incomum ver estudantes iniciando seus doutorados com apenas um conhecimento limitado em matemática e nos aspectos formais da ciência da computação. Obviamente, será muito difícil para esses estudantes se tornarem cientistas da computação teóricos, mas seria bom que eles pudessem se tornar...
Dado um sistema de transição rotulado (S,Λ,→)(S,Λ,→)(S,\Lambda,\to) , onde SSS é um conjunto de estados, ΛΛ\Lambda é um conjunto de rótulos e →⊆S×Λ×S→⊆S×Λ×S\to\subseteq S\times\Lambda\times S é uma relação ternária. Como sempre, escreva p→αqp→αqp \stackrel\alpha\rightarrow q para . A transição...
Eu tenho uma atribuição na qual preciso usar uma árvore de pesquisa binária e alterá-la para se auto-ordenar, de modo que os itens mais acessados (tenham uma prioridade mais alta) estejam no topo da árvore, a raiz sendo o nó mais acessado . O professor me deu o BST e a estrutura do nó para...
Este é um quebra-cabeça sobre como medir a latência da rede que eu criei. Acredito que a solução é que é impossível, mas os amigos discordam. Estou procurando explicações convincentes de qualquer maneira. (Embora seja apresentado como um quebra-cabeça, acho que se encaixa neste site devido à sua...
Vamos haver algum conjunto finito de caracteres de tamanho fixo. Seja α um fio acima de Σ . Dizemos que um substrato não vazio β de α é uma repetição se β = γ γ para alguma cadeia γ .ΣΣ\Sigmaαα\alphaΣΣ\Sigmaββ\betaαα\alphaβ= γγβ=γγ\beta = \gamma \gammaγγ\gamma Agora, minha pergunta é se o seguinte...
Estou aprendendo sozinho os provedores de teoremas automatizados / solucionadores de SMT / assistentes de prova e postar uma série de perguntas sobre o processo, começando aqui . Quais são os provadores de teoremas automatizados relevantes? Encontrei uma revisão dos provedores de teoremas Ainda...
Encontrei as seguintes dúvidas sobre a complexidade das Torres de Hanói , sobre as quais gostaria de seus comentários. Está em NP? Resposta da tentativa: Suponha que Peggy (provador) resolva o problema e o envie a Victor (verificador). Victor pode ver facilmente que o estado final da solução...