Seja um gráfico incorporado em uma superfície compacta orientável do gênero modo que a incorporação seja celular. Considere o duplo do gráfico . Sejam e ciclos disjuntos em que são homotópicos entre si e que eGGGgggG∗G∗G^*C1C1C_1C2C2C_2G∗G∗G^*E1E1E_1E2E2E_2 sejam seus conjuntos de arestas...
Estou pesquisando a dimensão VC do seguinte sistema definido. Universo tal que U ⊆ R 3 . No sistema de conjuntos R, cada conjunto S ∈ R corresponde a uma esfera em R 3, de modo que o conjunto S contém um elemento em U se e somente se a esfera correspondente o contém em R 3 .você= { p1 1, p2, … ,...
Em uma pergunta anterior parametrizada algoritmo para encontrar Bicliques , perguntei se não foram rápido parametrizada algoritmos para encontrar um -biclique em uma n grafo vértice e aprendeu que foi aberto se é FPT wrt k . É o mesmo verdade para contar o k × k -bicliques, ou é conhecido que este...
Gostaria de me desculpar por todos os posts abaixo. Escolheu o fórum errado para postar isso originalmente. No entanto, em vez de tornar isso um desperdício completo, refiz a pergunta como um verdadeiro problema "Ciência da Computação Teórica". Problema: Crie um algoritmo que utilize um conjunto...
Seja um quadrado unitário. Em função de , qual é o número máximo de regiões gorduras desniveladas aos pares com diâmetro pelo menos 1 que pode cruzar ?SSSββ\betaββ\betaSSS Abaixo, fornecemos uma figura mostrando que para , o número máximo é 7. E quanto a ?β= 1β=1 1\beta=1β= 2 , 3 , … ,...
Existem alguns problemas de NP-Complete ( , , etc.) conhecidos por estarem em . E os espaços sub-lineares?S U B S E T S U MSATSAT \mathsf{SAT} SUBSETSUMSUBSETSUM \mathsf{SUBSETSUM} DSPACE(n)DSPACE(n) \mathsf{DSPACE(n)} Existe algum problema NP-Completo (ou NP-Intermediário) no espaço sub-linear...
Pelo título, além de usar um propósito LP solver geral, existe uma abordagem para sistemas de desigualdades mais variáveis resolver xi,…,xkxi,…,xkx_i, \ldots, x_k onde as desigualdades têm a forma ∑i∈Ixi<∑j∈Jxj∑i∈Ixi<∑j∈Jxj\sum_{i \in I} x_i < \sum_{j \in J} x_j ? E o caso especial de...
Esta é uma pergunta que fiz no fórum de matemática SE, e fui encaminhada aqui. Então aqui está a questão- Eu sou um novato em matemática formal e em ciência da computação teórica, então, por favor, tenha paciência comigo se achar que minha pergunta não está devidamente enquadrada. A Modelagem...
Suponha que tenhamos um gráfico em nnn nós. Gostaríamos de atribuir a cada nó um +1+1+1 ou um −1−1−1 . Chame isso de configuração σ∈{+1,−1}nσ∈{+1,−1}n\sigma \in \{+1,−1\}^n . O número de +1+1+1 s que devemos atribuir é exatamente sss (portanto, o número de −1−1−1 s é n−sn−sn−s .) Dada uma...
Estou procurando um teorema que diga algo assim: se o tempo de cobertura de uma cadeia reversível de Markov é pequeno, então o intervalo espectral é grande. Aqui, o intervalo espectral significa, ou seja, ignoramos o menor autovalor da cadeia.1 - | λ2|1 1-|λ2|1-|\lambda_2| O único resultado que...
Editar: agora existe uma pergunta de acompanhamento relacionada a esta postagem. Definições Seja ccc e kkk números inteiros. Usamos a notação [i]={1,2,...,i}[i]={1,2,...,i}[i] = \{1,2,...,i\} . Um c×cc×cc \times c matriz M=(mi,j)M=(mi,j)M = (m_{i,j}) é dito ser um ccc Para- kkk coloração...
Eu pedi esse problema no MathOverflow , sem nenhuma resposta satisfatória. Considere o seguinte jogo para dois jogadores, que é uma simplificação do jogo de cartas chamado Winner . (A formulação a seguir foi retirada de um comentário de Guillaume Brunerie no MathOverflow.) Existem dois jogadores...
Estou procurando um algoritmo para desenhar um gráfico misto de constituição / dependência (para um aplicativo linguístico). Esse gráfico teria dois tipos diferentes de vértices (tokens, nós) e dois tipos diferentes de arestas (hierárquica, não hierárquica). Eu sou novo na teoria dos grafos e...
Tenho lutado com os detalhes técnicos de uma prova relativa à teoria dos leilões neste artigo: http://users.eecs.northwestern.edu/~hartline/omd.pdf Teorema 2.5: As condições necessárias e suficientes para um mecanismo verdadeiro. Ainda mais especificamente, a direção para a frente da prova, dada...
Estou trabalhando no campo da engenharia estrutural e gostaria de encontrar um algoritmo eficiente para construir uma aproximação (na métrica de Hausdorff) de um corpo convexo pelo casco convexo de n elipsóides, para alguns n fixos . Atualmente, estou trabalhando apenas nas dimensões 2 e...
Background––––––––––––––Background_\underline{\bf Background} Em 2005, Regev [1] introduziu o problema de Aprendizagem com Erros (LWE), uma generalização do problema de Paridade de Aprendizagem com Erros. A suposição da dureza desse problema para certas opções de parâmetro agora está subjacente às...
Minha pergunta é sobre teoria finita de modelos / complexidade descritiva, então significará "primeira ordem sobre palavras binárias finitas, usando os predicados Rs e um predicado unário P verdadeiro na posição do 1 na palavra".FO(R)FO(R)FO(R) Gostaria de saber, existe alguma caracterização de...
Essa é uma pergunta suave que visa estabelecer o que as pessoas pensam ser a melhor prática profissional para enviar trabalho não original ao arXiv. Há um rascunho de um artigo [1] de Robert Szelepcsényi, em seu espaço na Web da Universidade de Chicago, aparentemente escrito há mais de uma década...
Eu sei que o esperado pior caso de tempo de execução do randomizado incrementais Delaunay triangulação algoritmo (como indicado no Computational Geometry ) é . Há um exercício que implica que o pior tempo de execução é . Eu tentei construir um exemplo em que esse é realmente o caso, mas ainda não...
XXXΣnΣn\Sigma^nΣΣ\SigmaH(X)≥(n−δ)⋅log|Σ|H(X)≥(n−δ)⋅log|Σ|H(X) \ge (n- \delta)\cdot\log|\Sigma|δδ\deltaE⊆Supp(X)E⊆Supp(X)E \subseteq \rm{Supp}(X)XXXPr[X∈E]≥1−εPr[X∈E]≥1−ε\Pr[X \in E] \ge 1 - \varepsilonεε\varepsilon Dizemos que um par é uma coordenada de baixa probabilidade de se . Dizemos que uma...