Houve algum estudo para determinar se a inteligência humana pode superar os algoritmos (ou seja, testar se o Teorema Sem Almoço Gratuito se aplica à inteligência humana)? Na mesma linha, alguém desenvolveu um método técnico para tirar proveito de quaisquer propriedades supra-computacionais únicas...
Suponha que NP = co-NP e polinômio limita o comprimento da prova de insatisfação para uma instância 3-CNF x . Então, existem resultados de que forma qualquer prova de insatisfação para x de comprimento ≤ p ( x ) pode levar? Ou seja, em geral, essa prova teria que, por exemplo, usar todo o poder da...
O que se segue pode parecer estúpido (e isso provavelmente reflete meu fraco entendimento - por isso, tenha paciência comigo) Eu tive uma consulta no teorema do PCP. Sabemos que após os três primeiros passos viz. Redução de Grau, Expansão e Amplificação de Gap, temos um gráfico de restrição com...
Ultimamente, tenho aprendido sobre provas interativas e me pergunto se tudo não passava de uma curiosidade teórica ou se havia alguma aplicação prática. Pensei em começar com um exemplo que me ocorreu no chuveiro: Ultimamente, tem divulgado que "Número de Deus" = 20. (O número de Deus é o número...
Desculpe se estou enganado com o local para fazer a pergunta (talvez eu deva ir para stackoverflow.com/mathoverflow.net?). Gostaria de saber se existe uma prova de que, ao avaliar o algoritmo euclidiano estendido, os coeficientes de Bézout (que são s e t na identidade como + bt = gcd ( a , b ))...
Esta é uma continuação da minha pergunta anterior sobre limites inferiores de comunicação para funções booleanas parciais . Alguém pode sugerir alguma referência nos limites inferiores para comunicação multipartidária não determinística? Venho pesquisando os artigos em campo, mas todo mundo parece...
Jogos de uma rodada com dois provadores (2P1R) são uma ferramenta essencial para a dureza da aproximação. Especificamente, a repetição paralela de jogos de uma rodada com dois provadores oferece uma maneira de aumentar o tamanho de uma lacuna na versão de decisão de um problema de aproximação. Veja...
Na complexidade parametrizada, as pessoas usam a redução de FPT (Trace-Parametrable-Fixed) para provar a dureza W [t]. Teoricamente, uma redução de FPT não é uma redução de tempo polinomial, pois pode ser executada exponencialmente no parâmetro k. Mas, na prática, todas as reduções de FPT que eu vi...
Eu estava lendo um artigo intitulado Random Oracles com (fora) programação . O último parágrafo da seção 2.3 diz: [Usando nossa nova abordagem], não há necessidade de aplicar técnicas clássicas conhecidas de derandomização assintótica (e uniforme) com base no lema de Borel-Cantelli . Até onde...
Como 2 problemas completos de NP são por definição redutíveis um ao outro, portanto, uma solução para um deles pode ser obtida usando uma caixa preta para resolver o outro, por que eles não têm taxas de aproximação semelhantes (consultando as contrapartes de otimização) )? Eu acho que algum desvio...
Seja um gráfico direcionado acíclico, de modo que o grau externo de qualquer vértice seja O ( log | V | ) . Para cada vértice de G , podemos contar o número de vértices alcançáveis, apenas executando dfs de cada vértice e isso levará tempo O ( | V | | E | ) . Existe uma maneira melhor de resolver...
Quais são os obstáculos para tornar competitivos os solucionadores SAT com algoritmos gráficos especializados? Em outras palavras, é possível esperar solucionadores SAT que possam substituir o papel de projetista de algoritmos - ou seja, ser capaz de reconhecer automaticamente a estrutura do...
\newcommand{\symp}{\Bumpeq} Uma relação de coerência ≎X≎X\symp_X em um conjunto XXX é uma relação reflexiva e simétrica. Um espaço de coerência é um par (X,≎X)(X,≎X)(X, \symp_X) , e um morfismo f:X→Yf:X→Yf : X \to Y entre espaços de coerência é uma relação f⊆X×Yf⊆X×Yf \subseteq X \times Y tal que...
Existe uma classe de algoritmos de hash, teóricos ou práticos, de modo que um algoritmo na classe possa ser considerado 'reflexivo' de acordo com uma definição dada abaixo: hash1 = algo1 ("texto de entrada 1") hash1 = algo1 ("texto de entrada 1" + hash1) O operador + pode ser concatenação ou...
Angluin e Laird ('88) formalizaram o aprendizado com dados corrompidos aleatoriamente no modelo "PAC com ruído de classificação aleatória" (ou ruído barulhento). Esse modelo é semelhante ao aprendizado do PAC , exceto que os rótulos dos exemplos dados ao aluno estão corrompidos (invertidos),...
Esta pergunta foi motivada por uma pergunta no stackoverflow . Suponha que você está dado uma árvore enraizada (ou seja, há uma raiz e nós ter filhos, etc.) em n nós (rotulados 1 , 2 , ... , n ).TTTnnn1,2,…,n1,2,…,n1, 2, \dots, n Cada vértice tem um peso inteiro não negativo associado: w i...
Eu sou um estudante de CS. Fizemos teoria dos grafos em um curso. Achei interessante. Quais são as reais aplicações da teoria dos grafos no campo da ciência da computação? Por exemplo, descobri que alguns conceitos na teoria dos grafos podem ser usados para projetar redes. Quais são outras...
A segurança do SHA-1 foi discutida desde que um algoritmo para encontrar colisões foi publicado pela primeira vez no CRYPTO 2004 e posteriormente aprimorado. A Wikipedia lista algumas referências , no entanto, parece que a pesquisa mais recente publicada (e mais tarde retirada) sobre esse assunto...
Merlin, que possui recursos computacionais ilimitados, quer convencer Arthur de que para com e O cálculo dessa soma da maneira direta (exponenciação e adição modular) leva tempo com multiplicação baseada em FFT. * Mas Arthur só pode executar operações . ( N , m , k
Estou tentando encontrar problemas cuja complexidade de espaço de caso médio foi analisada. Mais especificamente, estou interessado em saber se existem problemas com um limite inferior da complexidade de espaço comprovado que é super-linear e, especialmente, se houver algum com uma análise de...