Existe uma maneira de provar o seguinte teorema em Coq? Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2. EDIT : Uma tentativa de dar uma breve explicação sobre "o que é irrelevância para a prova" (corrija-me alguém se eu estiver errado ou impreciso) A idéia básica é que, no...
Eu tenho muitos cuboides no espaço 3D, cada um tem um ponto de partida em (x, y, z) e tem tamanho de (Lx, Ly, Lz). Gostaria de saber como encontrar um cubo maior neste espaço 3D que está contido na união dos cuboides. Existe um algoritmo eficiente para isso? Por exemplo, se eu tiver os seguintes...
É sabido que se , a hierarquia polinomial entra em colapso e .P=NPP=NP\mathbf{P}=\mathbf{NP}P=PHP=PH\mathbf{P}=\mathbf{PH} Isso pode ser facilmente entendido por indução usando máquinas oracle. A questão é: por que não podemos continuar o processo indutivo além de um nível constante de alternância...
Alguém pode explicar brevemente (se isso for possível!) Ou me referir a uma referência, resumindo as diferenças entre o cálculo lambda não digitado e o cálculo lambda digitado mais comum? Estou particularmente procurando declarações de seu poder expressivo, equivalências a sistemas lógicos /...
Estou revisando o Manual de computação inovadora e inspirada na natureza para o SIGACT News. É uma leitura muito interessante. Cada capítulo, no entanto, tem o sabor: "Esta é a minha área de pesquisa e, caramba, é incrível!" Portanto, parte do que estou tentando fazer é separar o hype e fazer uma...
Em 1979, Freivalds mostrou que a verificação de produtos matriciais em qualquer campo pode ser feita em tempo aleatório O(n2)O(n2)O(n^2). Mais formalmente, dadas três matrizes A, B e C, com entradas de um campo F, o problema de verificar se AB = C possui um algoritmo de tempo aleatório...
Meu filho de 8 anos se cansou de criar labirintos convencionais e passou a criar variantes que se parecem com isso: A idéia é começar de x e alcançar o através das regras normais. Além disso, você pode "saltar" de qualquer número inteiro para qualquer outro número inteiro b , mas você deve pagar...
Esta é uma reformulação dos programas de gramática São? solicitado anteriormente por Vag e com muitas sugestões dos comentaristas. De que maneira uma gramática pode ser vista como especificando um modelo de computação? Se, por exemplo, usarmos uma gramática simples, livre de contexto, como G ::=...
Isso pode ser considerado uma pergunta estúpida. Eu não sou formado em ciência da computação (e também não sou formado em matemática), então, desculpe-me se você acha que as seguintes perguntas apresentam algumas suposições errôneas importantes. Embora haja planos para formalizar o Último Teorema...
Uma abordagem recente para criar uma moeda online descentralizada, chamada Bitcoin , vem gerando algum interesse. O objetivo é ter uma maneira de transferir moeda sem uma autoridade central e sem gastos duplos ou falsificações. Sua abordagem é fazer com que todos os nós da rede tentem verificar uma...
Aqui, o objetivo é reduzir um problema arbitrário de SAT para 3-SAT em tempo polinomial usando o menor número de cláusulas e variáveis. Minha pergunta é motivada pela curiosidade. Menos formalmente, eu gostaria de saber: "Qual é a redução 'mais natural' de SAT para 3-SAT?" Agora, a redução que eu...
( n + 1 )(n+1)(n + 1) pontos são necessários para determinar exclusivamente um polinômio de graunnn ; por exemplo, dois pontos em um plano determinam exatamente uma linha. Quantos pontos são necessários para determinar exclusivamente uma função computável f: N→ Nf:N→Nf : N \rightarrow N , dada a...
Trabalhar diretamente com complexidade de tempo ou limitar os limites inferiores do circuito é assustador. Por isso, desenvolvemos ferramentas como complexidade da consulta (ou complexidade da árvore de decisão) para lidar com limites inferiores. Como cada consulta executa pelo menos uma etapa da...
Por curiosidade, se a computação clássica é sobre matrizes de permutação e a computação quântica é sobre matrizes unitárias (das quais as matrizes de permutação são um subgrupo), haverá algum paradigma de computação além das matrizes
EDIT (22 de agosto de 2011): Estou simplificando ainda mais a questão e colocando uma recompensa nela. Talvez esta pergunta mais simples tenha uma resposta fácil. Também vou rascunhar todas as partes da pergunta original que não são mais relevantes. (Obrigado a Stasys Jukna e Ryan O'Donnell por...
O problema da satisfação é, obviamente, um problema fundamental no CS teórico. Eu estava brincando com uma versão do problema com infinitas variáveis. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Configuração básica. Seja XXX um conjunto de variáveis não vazio e...
Qual é a complexidade (na RAM inteira padrão) de calcular a transformada discreta padrão de Fourier de um vetor de números inteiros?nnn O algoritmo clássico para transformações rápidas de Fourier , atribuídas inadequadamente [1] a Cooley e Tukey, é geralmente descrito como sendo executado em tempo...
Eu acho que não estou entendendo isso, mas -conversion me parece uma conversão que não faz nada, um caso especial de -conversion em que o resultado é apenas o termo na abstração lambda porque não há nada para fazer, uma espécie de conversão inútil .β β βηη\etaββ\betaββ\betaββ\beta Portanto, talvez...
Existem vários algoritmos que podem analisar uma gramática livre de contexto em . Usando a multiplicação de matrizes, pode-se até assintoticamente mais rápido que isso.O ( n3)O(n3)O(n^3) No entanto, todos os algoritmos para analisar CFGs arbitrários que eu conheço têm um uso de espaço no pior dos...
A operação de votação majoritária ocorre com bastante frequência na tolerância a falhas (e sem dúvida em outros lugares), onde a função gera um bit igual ao valor sempre exibido com mais freqüência no valor dos bits de entrada. Por uma questão de simplicidade, vamos assumir que sempre que a entrada...