45 artigos
Este artigo apresenta uma descrição completa e otimizada de um algoritmo que estima o grau médio de grafos com arboricidade limitada, eliminando fatores logarítmicos desnecessários e alcançando uma complexidade de consulta de .
Este trabalho estabelece novas separações entre classes de circuitos quânticos de profundidade constante (incluindo aqueles com Toffoli de controle ilimitado e dicas quânticas) e circuitos clássicos, demonstra que circuitos quânticos de profundidade constante com conjuntos de portas infinitos podem implementar portas de limiar e prova que espaços de Hilbert de dimensão superior não oferecem vantagem sobre implementações de qubits nesse contexto.
Este artigo inicia um estudo sistemático da complexidade computacional no teste de propriedades, estabelecendo teoremas de hierarquia entre consultas e tempo de execução e provando limites inferiores finos para a aproximação de distância a semiespaços, revelando assim uma separação fundamental entre a complexidade de consultas e a de tempo.
Este artigo demonstra que determinar se uma estratégia computável é vencedora em Yu-Gi-Oh! TCG é um problema indecidível e, na verdade, -completo, reduzindo o problema da parada e o conjunto de ordens bem-ordenadas contáveis a cenários de jogo utilizando decks legais.
Este artigo propõe uma análise unificada da assimetria fundamental entre geração e reconhecimento em teoria das linguagens formais, identificando seis dimensões distintas (complexidade computacional, ambiguidade, direcionalidade, disponibilidade de informação, inferência de gramática e temporalidade) para demonstrar que a distinção clássica de "geração fácil, análise difícil" é enganosa e que a verdadeira assimetria reside no fato de que a análise é sempre restrita por uma entrada dada, enquanto a geração não necessariamente o é.
Esta habilitação apresenta algoritmos eficientes em tempo e espaço para computações polinomiais fundamentais e explora a interpolação e fatoração de polinômios esparsos, abordando como as restrições de memória impactam a complexidade computacional em cenários densos e esparsos.
Este artigo estabelece condições necessárias e suficientes para a simulabilidade clássica de circuitos quânticos seguidos por pós-processamento clássico esparsos, demonstrando que certas classes de circuitos quânticos tornam-se simuláveis sob essas condições e que circuitos de profundidade constante podem ser simulados probabilisticamente com acesso a circuitos quânticos comutativos.
O artigo propõe uma reinterpretação da descoberta de testemunhas em problemas NP sob uma ótica teórica da informação, demonstrando que, no modelo "psocid" sem estrutura, a redução da incerteza necessária para a recuperação confiável exige uma quantidade de informação que excede em muito a capacidade de aquisição das consultas de igualdade, revelando assim uma origem informacional fundamental para a complexidade exponencial da busca.
Este artigo demonstra que o problema de Coloração Parcial de Lista Máxima em H é solúvel em tempo polinomial em grafos livres de P₅ para qualquer grafo H fixo, resolvendo uma questão em aberto e melhorando algoritmos anteriores.
Este artigo investiga a complexidade de representação de fórmulas CNF com largura de árvore limitada no modelo Decision DNNF, estabelecendo limites inferiores para subclasses como -OBDD, propondo uma metodologia para provar tais limites, analisando a operação Apply e introduzindo o modelo relaxado Structured -FBDD, que se mostra eficaz para CNFs de largura de árvore de incidência limitada.
Este artigo apresenta algoritmos clássicos eficientes para os problemas e de Solução Inteira Constrained, demonstrando que não há mais aceleração quântica exponencial para essas instâncias, invalidando assim os resultados anteriores de Chen, Liu e Zhandry.
Este artigo apresenta um novo algoritmo de aproximação com razão $4/3O(m\sqrt{n})$ superior aos métodos anteriores baseados em programação linear ou enumeração.
Este artigo apresenta uma classificação completa da complexidade computacional distribuída de problemas de otimização local em ciclos direcionados, demonstrando que, para qualquer problema e razão de aproximação, a complexidade pertence a uma de quatro classes específicas e pode ser determinada automaticamente por um meta-algoritmo eficiente que também sintetiza algoritmos distribuídos assintoticamente ótimos.
Este artigo estabelece uma conexão teórica fundamental entre complexidade computacional e arquiteturas de redes neurais, demonstrando que as RNNs lineares são altamente paralelizáveis por pertencerem à classe (semelhante aos Transformers), enquanto as RNNs não lineares enfrentam barreiras de paralelização ao resolverem problemas completos em ou .
Este artigo propõe uma abordagem integrativa para a seleção justa de top- que generaliza cenários anteriores para múltiplos grupos protegidos, analisa a complexidade computacional do problema, introduz uma nova medida de disparidade baseada em perda de utilidade para maior estabilidade e apresenta uma solução prática com alto desempenho empírico em conjuntos de dados reais.
Este artigo apresenta a implementação de algoritmos quânticos baseados na busca de Grover para resolver o problema de Coordenação de Sinais de Rede (NSC) e sua versão robusta, demonstrando uma aceleração quadrática na complexidade computacional através de simulações e execução em um computador quântico real.
Este artigo apresenta o algoritmo ResultantSolver, que resolve um sistema polinomial específico sobre um corpo finito explorando sua esparsidade estruturada através de resultantes sucessivas, alcançando uma eficiência significativamente superior às abordagens de força bruta e bases de Gröbner padrão.
Este artigo estabelece uma correspondência exata entre o poder computacional de redes neurais em grafos recorrentes e circuitos aritméticos recorrentes sobre números reais, demonstrando que ambas as arquiteturas possuem expressividade equivalente ao simularem mutuamente suas respectivas computações.
Este artigo resolve uma questão em aberto sobre a complexidade do problema de Correspondência de Morse Ótima em complexos de largura de árvore limitada, apresentando um algoritmo de tempo $2^{O(k \log k)} n$ e provando que essa dependência é ótima sob a Hipótese do Tempo Exponencial (ETH).
Este artigo demonstra que a conjectura de Aaronson-Ambainis é válida para uma fração não desprezível de restrições aleatórias de polinômios de grau com variância suficientemente alta, provando que, sob tais restrições, existe uma coordenada com influência significativamente grande com probabilidade não trivial.