Muitos recursos relacionados a noções categóricas na programação descrevem mônadas, mas nunca vi uma descrição categórica de transformadores de mônada. Como os transformadores de mônada podem ser descritos nos termos da teoria das categorias? Em particular, eu estaria interessado em: a relação...
Quando tentamos construir um algoritmo para um novo problema, dividir e conquistar (usando recursão) é uma das primeiras abordagens que tentamos. Mas, em alguns casos, essa abordagem parece infrutífera à medida que o problema se torna muito mais complicado à medida que sua entrada cresce. Minha...
Existe alguma semântica categórica para lógicas não monotônicas? Parece que a resposta simples para isso é "Não", pois a noção óbvia de composição falha em qualquer modelo de lógica não monotônica. Mas existe um modelo que realmente funcione com uma noção de composição adequadamente...
Minha pergunta diz respeito à prova do principal teorema de Ajtai em seu artigo inovador de 1996, Gerando instâncias rígidas de problemas de treliça , o que indica uma conexão entre os problemas de treliça de pior caso e de malha dura de caso médio. Esta prova é difícil para mim entender. Existe...
Existem alguns teoremas, principalmente na teoria dos grafos e na otimização combinatória, que são frequentemente referidos como boas caracterizações. Eles tipicamente colocam uma propriedade em , mostrando que uma propriedade é válida ou existe algum obstáculo bem identificado que a impede de ser...
De acordo com o XOR Satisfiability Solver Module para integração de DPLL por Tero Laitinen, precisamos de cláusulas n - 1 CNF para converter uma cláusula XOR-SAT n literal se não quisermos aumentar o número de literais. Portanto, entendo que o custo computacional para converter uma expressão...
Eu tenho trabalhado em um projeto independente com foco em autômatos celulares e queria saber se isso poderia ser algo que eu poderia continuar na pós-graduação em algum lugar. Eu já vi alguns departamentos de matemática com dinâmica simbólica, bem como alguns departamentos de CS com pesquisadores...
Suponha que, para um dado problema de minimização com apenas soluções inteiras, seja difícil decidir se a solução ideal é 5 ou 6. Ou seja, um algoritmo de tempo polinomial com uma taxa de aproximação melhor que 6/5 implicaria P = N P .NPNPNPP= NPP=NPP=NP 1) Será que isso implica que o problema é...
Um gráfico é localmente bipartido se a vizinhança aberta de cada vértice induzir um gráfico bipartido. (De acordo com as pesquisas, o mesmo nome pode ser usado para algo mais relacionado a superfícies). Quais problemas difíceis de NP para gráficos gerais se tornam polinomiais para gráficos...
Parece-me que a tarefa de remoção de quadrados pode ser reduzida à tarefa de fatoração , mas que não há como reduzir o fatoramento à remoção de quadrados. Existe uma maneira de tornar esse "sentimento" mais preciso, ou seja, alguma hipótese comumente considerada que seria violada se o fatoramento...
Para as complexidades de Kolmogorov induzidas por linguagens de descrição essencialmente ótimas, existe um número inteiro tal que, para todos os números inteiros positivos , exista uma cadeia tal que?KK\hspace{.02 in}Kcccnnnxxxn<K(x)<n+cn<K(x)<n+c\;\;\; n \: < \: K(x) \: < \:...
Eu vi esse problema: Uma sequência não crescente de números inteiros positivos é n-realizável se o conjunto puder ser particionado em subconjuntos mutuamente separados tal que para cada .I n = { 1 , 2 , . . . , N } k S 1 , S 2 , . . . , S k ∑ x ∈ S i x = m i 1 ≤ i ≤...
No filme Inception, Cobb pede a Ariadne para projetar um labirinto que leva o dobro do tempo para projetar. Isso se presta a um problema generalizado em que temos uma situação em que temos recursos limitados em alguma quantia e quem verificará se esse problema está na classe de complexidade...
Seja um problema gráfico completo de NP. Suponha que X seja solucionável em tempo polinomial em gráficos de diâmetro delimitado. Em outras palavras, X parametrizado por diâmetro está no XP. (Lembre-se de que um problema está no XP se ele puder ser resolvido no tempo n f ( k ) ). Isso implica...
Seja SAT o idioma das instâncias do SAT que contêm variáveis , seja -SAT o idioma das instâncias do SAT nas quais todas as cláusulas têm no máximo k literais, e deixe k -SAT _v ser sua interseção. Seja s_k = \ inf_M \ {\ delta \ mid \ existe c \ forall v \; (M \ text {decide} k \ text {-SAT $ _v $...
Existe um resultado de impossibilidade condicional ou a pergunta está completamente
O Modelo Padrão da física (o modelo matemático que prediz o bóson de Higg) é, até onde eu entendo, o nosso modelo mais completo do universo. Ou seja, é a melhor descrição do jogo matemático a ser jogado para fazer previsões sobre o resultado dos experimentos realizados em nosso Universo. Pelo que...
A complexidade da comunicação (CC) é a única abordagem conhecida para algoritmos de streaming com limites mais baixos? Existem outras técnicas, mesmo que limites inferiores condicionais ? Em geral, estamos satisfeitos com o progresso alcançado via CC? Ou buscar técnicas alternativas (mesmo que...
\newcommand{\cc}[1]{\mathsf{#1}} Um teorema ao longo das seguintes linhas é válido: Se é um pouco maior que , então ?g(n)g(n)g(n)f(n)f(n)f(n)NTIME(g)∩coNTIME(g)≠NTIME(f)∩coNTIME(f)NTIME(g)∩coNTIME(g)≠NTIME(f)∩coNTIME(f)\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(f) É...
Me deparei com uma apresentação de Ryan O'Donnell sobre princípios de invariância. Depois de provar o teorema de Berry-Esseen, há um slide que discute extensões do teorema e um que é mencionado, há a chamada "versão derandomizada": Se C- bom (isto é, limitou o terceiro momento), independente em...