O que se sabe sobre a transição de fase nos problemas # P-Complete? Especificamente, existe uma transição de fase diferente para # DNF-k-SAT e # CNF-k-SAT? Atualização: Como sabemos, há uma transição de fase no Random k-SAT em que a solução do problema passa de fácil a difícil e volta a fácil...
Como se olha para um problema e o motivo pelo qual é provável NP-Intermediário em oposição a NP-Complete? Muitas vezes, é bastante simples olhar para um problema e dizer se é provável que o NP-Completo seja ou não, mas me parece muito mais difícil dizer se um problema é NP-Intermediário, pois a...
Esta pergunta está relacionada a uma pergunta recente de Janoma . fundo Na programação restrição, um normal global de restrição ao longo de um domínio é um par (S, M) com s um tuplo de variáveis (o escopo) e M um DFA sobre o domínio D . Uma atribuição \ theta a s satisfaz c se M aceitar a...
Eu acho que seria chamado # P-Space, mas eu encontrei apenas um artigo mencionando-o vagamente. Que tal a versão de contagem dos problemas EXP-TIME-Complete, NEXP-Complete e EXP-SPACE-Complete? Existe algum trabalho anterior que se possa citar em relação a esse ou a qualquer tipo de inclusão ou...
O problema tradicional da galeria de arte configura uma região e os guardas com alguma noção de visibilidade e solicita o número mínimo de guardas que precisam ser colocados para ver toda a região. Alguém já olhou as variantes da galeria de arte em que a região de visibilidade é definida por um...
Suponha que tenhamos um semigrupo com os elementos S = { s 1 , s 2 , … , s n } . Nosso objetivo é produtos de computação s i ∘ s i + 1 ∘ ⋯ ∘ s j .(S,∘)(S,∘)(S,\circ)S={s1,s2,…,sn}S={s1,s2,…,sn}S=\lbrace s_1,s_2,\dots,s_n\rbracesi∘si+1∘⋯∘sjsi∘si+1∘⋯∘sjs_i\circ s_{i+1}\circ \cdots\circ s_j Em seu...
Nos sistemas de controle de versão distribuído (como Mercurial e Git ), é necessário comparar eficientemente os gráficos acíclicos direcionados (DAGs). Sou desenvolvedor da Mercurial e gostaríamos muito de ouvir sobre o trabalho teórico que discute a complexidade de tempo e rede da comparação de...
Dado um gráfico não direcionado ponderado com m=o(n2)m=o(n2)m = o(n^2) arestas, eu gostaria de calcular distâncias de aproximação inferiores a 2 entre qualquer par de vértices. Obviamente, eu gostaria de usar o espaço subquadrático e o tempo de consulta sublinear. Estou ciente do resultado de...
Existem problemas cuja complexidade média de casos é a mesma de pior complexidade? Quais são as propriedades subjacentes a esses problemas que tornam possível reduzir o pior caso para o caso
Estou interessado em uma variação de SAT em que a fórmula CNF é monótona (nenhuma variável é negada). Essa fórmula é obviamente satisfatória. Mas digamos que o número de variáveis verdadeiras seja uma medida de quão boa é a nossa solução. Portanto, temos o seguinte problema: MONOTONE VERDADEIRO...
Esta pergunta pode não ser técnica. Como um falante não-nativo e um AT para a classe de algoritmos, sempre me perguntei o que significa gadget em 'cláusula gadget' ou 'variável gadget'. O dicionário diz que um gadget é uma máquina ou um dispositivo, mas não tenho certeza do significado coloquial...
Seja uma sequência de números inteiros em que cada um é um j ∈ { 1 , 2 , … , n } . Para i ∈ { 1 , 2 , … , n } , deixe m i = | { j : a j = i } | . O k th momento frequência é definida como sendoa1,a2,…,ama1,a2,…,ama_1, a_2,\dotsc, a_maj∈{1,2,…,n}aj∈{1,2,…,n}a_j \in...
Algoritmos de aproximação podem gerar um fator constante na saída. Isso é um pouco menos satisfatório do que algoritmos exatos. No entanto, fatores constantes são ignorados na complexidade do tempo. Então, eu me pergunto se o seguinte truque é possível ou foi usado, para resolver algum problema...
Pelo que entendi, na ciência da computação, os tipos de dados não são baseados na teoria dos conjuntos por causa de coisas como o paradoxo de Russell, mas como nas linguagens de programação do mundo real, não podemos expressar tipos de dados tão complexos como "conjunto que não se contém", podemos...
O exercício a seguir foi entregue aos alunos que eu supervisiono: Dados nnn pontos no plano, crie um algoritmo que encontre um par de pontos cuja distância seja mínima entre todos os pares de pontos. O algoritmo deve ser executado no tempo o ( n2)o(n2)o(n^2) . Existe um algoritmo de divisão e...
Recentemente, iniciei meu curso de mestrado. No semestre passado, participei de cursos de diferentes disciplinas, como redes, engenharia de software, arquitetura etc. Recentemente, depois de fazer um curso avançado em algoritmos e estruturas de dados, acho que encontrei um curso que me interessa...
Qual é a diferença de chamar -calculus uma álgebra em vez de um cálculo? Faço essa pergunta porque li em algum lugar a linha " -calculus não é um cálculo, mas uma álgebra" (iirc, atribuído a Dana Scott). Qual é o ponto?
EDIT (Por Tara B): Eu ainda estaria interessado em uma referência a uma prova disso, pois eu mesmo tinha que provar isso para o meu próprio artigo. Estou procurando a prova do Teorema 4 que aparece neste artigo: Uma hierarquia infinita de interseções de idiomas sem contexto por Liu e Weiner....
Trabalho em um laboratório de neurociência computacional que quantifica as informações mútuas entre pares ou grupos de neurônios. Recentemente, o chefe mudou seu foco para medir a "complexidade da dinâmica neural". Ao seguir essa linha de pesquisa, algumas pessoas no meu grupo parecem equiparar...
O problema da partição de 3 cliques é o problema de determinar se os vértices de um gráfico, digamos , podem ser particionados em 3 grupos. Esse problema é difícil de NP por uma simples redução do problema de 3 cores. Não é difícil ver que a resposta para esse problema é fácil quando ou . O...