Suponha que recebamos uma matriz A[1..n]A[1..n]A[1..n] contendo números inteiros não negativos (não necessariamente distintos). Deixe BBB ser AAA ordenado na ordem não crescente. Queremos calcular m=maxi∈[n]B[i]+i.m=maxi∈[n]B[i]+i.m = \max_{i\in [n]} B[i]+i. A solução óbvia é classificar AAA e...
A classe UP é definida como tal: A classe de problemas de decisão solucionáveis por uma máquina NP tal que Se a resposta for 'sim', exatamente um caminho de computação será aceito. Se a resposta for 'não', todos os caminhos de computação serão rejeitados. Estou tentando desenvolver...
O problema do "segundo " é o problema de decidir a existência de outra solução diferente de uma determinada solução, por exemplo.XXX Para algumas problemas -Complete, a segunda versão solução é -completo (decidir a existência de uma outra solução para o problema conclusão quadrado latino parcial),...
Impagliazzo, Paturi e Calabro, Impagliazzo, Paturi introduziram a Hipótese de tempo exponencial (ETH) e a Hipótese de tempo fortemente exponencial (SETH). Grosso modo, o SETH diz que não há algoritmo que resolva o SAT no tempo . 1.99n1.99n1.99^n Eu queria saber o que isso significaria para quebrar...
Estou procurando uma classe de complexidade que se relacione ao APX e o BPP ao P. Já fiz a mesma pergunta aqui , mas talvez o TCS seja um local mais proveitoso para respostas. A razão para a pergunta é que, em problemas práticos, geralmente é necessário encontrar respostas aproximadas (portanto...
Depois de ler uma pergunta relacionada , sobre provas não-construtivas de algoritmos, fiquei pensando se existem métodos para mostrar a existência de máquinas de computação "pequenas" (digamos, em termos de estado) sem realmente construí-la. Formalmente: suponha que recebamos alguma linguagem e...
Cruzado do MO . Seja CCC uma classe de gráfico definida por um número finito de subgráficos induzidos proibidos, todos cíclicos (contêm pelo menos um ciclo). Existem problemas de gráfico NP-rígido que podem ser resolvidos em tempo polinomial para CCC diferente da capa Clique e Clique? Se bem...
Isso me confunde. Um caso fácil de contagem é quando o problema de decisão está em e não há soluções.PPP Uma palestra mostra que o problema de contar o número de combinações perfeitas em um gráfico bipartido (equivalente a contar o número de capas de ciclo em um gráfico direcionado) é completo.#...
Considere o seguinte problema: Dadas duas cadeias x, y, decida se existe um homomorfismo da cadeia f tal que f (x) = y. É fácil mostrar que este problema está em . Há outras coisas que podemos dizer sobre esse problema? É por exemplo em C O N P , ou mesmo P ?NPNPNPcoNPcoNPcoNPPPP Esse...
Como sabemos, a definição de complexidade computacional do algoritmo é quase sem controvérsia, mas a definição de complexidade computacional de reais ou os modelos de computação sobre reais não é nesse caso. Conhecemos o modelo e o modelo de Blum e Smales no livro Análise Computável. E,...
Seja kkk algum campo. Como sempre, para um f∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in k[x_{1},x_{2},\ldots,x_{n}] , definimos L(f)L(f)L(f) como a complexidade linear de fff sobre kkk . Seja FFF o conjunto de monômios de fff , ou seja, os monômios que aparecem em fff com coeficiente diferente de zero....
Suponha que nossa entrada seja um binário e tenhamos que produzir ⌊ x / c ⌋ , onde c é um número inteiro constante. Isso é apenas uma mudança se c é uma potência de dois, mas e os outros números? Podemos fazer isso com um circuito de profundidade constante para cada c ? E quanto a c = 3...
Considere as informações completas sobre jogos combinatórios para dois jogadores que terminam após um número polinomial de jogadas e, de maneira alternada, os jogadores escolhem um número finito de jogadas permitidas. A pergunta usual é: quão difícil é distinguir de uma determinada posição o...
O problema do isomorfismo inverso semigrupo finito é GI-completo ? Aqui, supõe-se que os semigrupos inversos finitos sejam dados por suas tabelas de
Uma árvore de decisão de leitura única é definida da seguinte maneira: TrueTrueTrue e são árvores de decisão de leitura única.FalseFalseFalse Se e são árvores de decisão de leitura única e é uma variável que não ocorre em e , também é uma árvore de decisão leitura...
Eu estava pensando em qual classe esta língua pertence: é um grafo, k é um número natural e k é o número cromático de G }L={⟨G,k⟩∣GL={⟨G,k⟩∣GL =\{ \langle G,k \rangle \mid G kkkkkkG}G}G\} Pensei em como (1) "não há coloração de k-1 cores" e (2) "não há coloração de k- cores". Agora, (1) é coNP e...
Existem teoria algorítmica dos grafos / teoria dos números / combinatória / teoria da informação / teoria dos jogos. Existe análise matemática algorítmica? Segundo o wiki, a análise matemática inclui as teorias de diferenciação, integração, medida, limites, séries infinitas e funções...
Em resumo, a questão é: até que ponto, a capacidade computacional para tarefas difíceis realmente ajuda você a resolver tarefas fáceis. (Pode haver várias maneiras de tornar essa pergunta interessante e não trivial, e aqui está uma dessas tentativas.) Questão 1: Considere um circuito para...
Recentemente, me deparei com um artigo de Coudron e Yuen sobre expansão aleatória usando dispositivos quânticos. O principal resultado do trabalho é que é possível gerar aleatoriedade "infinita" a partir de um número constante de fontes (ou seja, o número de bits aleatórios gerados depende apenas...
Em uma fórmula CNF de leitura duas vezes oposta, cada variável aparece duas vezes, uma vez positiva e uma vez negativa. Estou interessado na problema, que consiste em calcular a paridade do número de satisfazer as atribuições de um oposto fórmula CNF leitura duas