Considere um politopo racional que é definido por meio de um oráculo de separação. Ou seja, pode ser descrito implicitamente como , mas como é muito grande, usamos um oracle, que dado um ponto , quer diz ou retorna uma meia-espaço de tal modo que .P P = { x ∈ R k : A x ≤ b , A ∈ Z m × k , b ∈ Z m }...
Qual é o maior conjunto que admite um algoritmo determinístico de busca quântica, para um único elemento marcado, que opera com apenas uma chamada para o oráculo? A questão é interessante, já que o algoritmo de Grover, que para pesquisa não estruturada em um conjunto de elementos requer chamadas...
Suponha que desejamos encontrar o menor elemento de um conjunto , cujos elementos são indexados de a . Não temos acesso aos valores desses elementos, mas podemos comparar quaisquer dois elementos de para ver qual é menor. Para quaisquer índices e , existe um associado custo para comparar o th e th...
Estou procurando fontes sobre a noção formalizada de programas. Isso parece estar intimamente relacionado à correspondência de Curry-Howard, mas também se pode rastrear isso na Universal Turing Machines e em sua capacidade de ler a descrição e a entrada de qualquer TM. Ao ler sobre a...
Eu gostaria de saber a importância do TCS na pesquisa de malware. Devido ao grande volume de novas variantes de malware recebidas por dia (~ 50.000 amostras / dia, de acordo com a McAfee), os pesquisadores de malware dependem fortemente da análise dinâmica (por exemplo, executando as amostras em...
Alguém conhece algum trabalho que vincule Ciência da Computação Teórica e Energia Barata / Sustentável? ou seja, existe algum trabalho no TCS com o aplicativo em energia barata /
Isso é conhecido sobre linguagens reconhecidas pelo autômato determinístico bidirecional bidirecional ou pelo logspace TM com contador (modelo equivalente)? Esta classe chamada Aux2DC no meu conselheiro papel . Ou sobre essa classe não determinística? Eu obtive que a classe de idiomas reconhecidos...
O seguinte problema é NP-difícil? Dado um conjunto de números reais (metas) e um "tridente" definido por duas distâncias , do centro do tridente, qual é o número mínimo de posições de o tridente para cobrir todos os alvos, por exemplo, x 1 , … , x N a b K p 1 , … , p K K ⋃ k = 1 { p k - a , p k ,...
É possível encontrar uma redução na contagem de #SAT para #HornSAT? Eu não encontrei esta pergunta postada aqui, então decidi verificar se alguém tem alguma resposta para isso. Deixe-me explicar o que quero dizer com contagem de redução. Suponha que são dois problemas de contagem. Por exemplo,...
No meu trabalho surgiu o problema da classificação CFL em imagens de funções racionais. Em outros termos, o que classe de linguagens formar línguas , para contexto fixo linguagem livre e transdutor de estados finitos determinística . Obtive alguns resultados fáceis, como a linguagem Dyck com duas...
Eu gostaria de um método eficiente para calcular o número mínimo de transposições necessárias para classificar uma lista. Não preciso saber quais são realmente as transposições. Por exemplo, a lista [1, 1, 2, 0] requer 2 transposições: [1, 1, 2, 0] // Start [1, 1, 0, 2] // Swap index 2 and 3 [0,...
Eu estava lendo sobre o problema da altura das estrelas e notei que a família de expressões regulares de Eggan segue um padrão simples que pode ser descrito por uma expressão regular. Minha pergunta é: existem resultados interessantes sobre expressões regulares que descrevem famílias de expressões...
Estou procurando o artigo original em que Hoare (ou outra pessoa, suponho) discute a rescisão (correção total). Ou qualquer outro trabalho inicial sobre rescisão para a lógica Hoare "baunilha" (suponho que quero dizer um HL para uma linguagem de brinquedo do tipo C). Dei uma olhada na base...
Eu tenho dois domínios totalmente distintos (maçãs e laranjas) e eu tenho uma função que pega um conjunto de objetos do primeiro domínio e um conjunto de objetos do segundo domínio e retorna um número real.fff possui as seguintes propriedades interessantes:f( S, T)f(S,T)f(S,T) fixando , é não...
No artigo de Savitch em 1969, "Relações entre complexidades de fita não determinísticas e determinísticas", ele afirma que "todas as funções comuns de armazenamento L (n)> = lg n são mensuráveis. Em particular, qualquer polinômio em n e lg n é mensurável". Sua definição de mensurável é: "Diz-se...
Não é difícil mostrar que classificar uma matriz de números é difícil para . Se a entrada é uma matriz de 1s e 0s então é essencialmente a função C o u n t (dado n bits de saída do número de 1s em binário) desde C S u n t é completo para o t C 0 e é possível converter números unários em números...
Provas simultâneas de zero conhecimento com complexidade redonda logarítmica Os números das páginas são do próprio papel e não do pdf. Na página 3, "Diz-se que um sistema interativo de prova é zero de caixa preta (computacional) se houver uma máquina de oráculo de tempo polinomial...
Funções lineares em uma variável têm dimensão VC = 3 e eu lembro de ler em algum lugar que o VC para polinômios de grau é .ddd(d2+3d+2)/2(d2+3d+2)/2(d^2 + 3d + 2)/2 Estou procurando idéias que possam provar a afirmação acima (e talvez generalize também para muitas variáveis, embora isso pareça...
Deixe ser um conjunto de tamanho e ser um conjunto de tamanho , para fixa e , e de tal modo que . Qual é a (ou a) família Sperner em para a qual é maximizada?k B ℓ k ℓ A ∩ B = ∅ F A ∪ B F B = { C ∩ B : C ∈ F }UMAAAkkkBBBℓℓ\ellkkkℓℓ\ellA ∩ B = ∅A∩B=∅A\cap B=\emptysetFF\mathcal{F}A ∪ BA∪BA\cup BFB= {...
Thor Johnson, et al., Em seu artigo: Directed Tree Width , introduziram uma definição para a grade direcionada , e eles conjeturaram:JkJkJ_k Para todo número inteiro k existe um número inteiro N tal que todo dígrafo com a largura da árvore N ou mais tem um menor isomórfico para J k...