Eu li aqui que existem famílias de funções que precisam de nós na rede neural com no máximo d - 1 camadas para representar a função e precisam apenas de O ( n ) se a rede neural tiver pelo menos d camadas. Referia-se a um artigo de Hastad. Eu não encontrei. Alguém poderia me dizer o título do...
Se NPNP\mathsf{NP} contiver uma classe de problemas de tempo superpolinomial, ou seja, para alguma função t∈nω(1)t∈nω(1)t \in n^{\omega(1)} , DTIME(t)⊆NPDTIME(t)⊆NP\mathsf{DTIME}(t) \subseteq \mathsf{NP} , P⊊NPP⊊NP\mathsf{P} \subsetneq \mathsf{NP} Mas existem outras conseqüências...
Para , seja o conjunto de vértices do cubo dimensional dimensionado na direção de a ésima coordenada por , ou seja, .Q( → d )⊂NnnidiQ( → d ={⟨±d1,...,±dn⟩}d⃗ ∈Nnd→∈Nn\vec{d} \in \mathbb{N}^nQ(d⃗ )⊂NnQ(d→)⊂NnQ(\vec{d}) \subset \mathbb{N}^nnnnEuiidEudEud_iQ ( d⃗ = { ⟨ ± d1, … , ± dn⟩...
Quando a conjectura ou P ≠ N P é definida (por exemplo, pelo Clay Mathematics Institute de S. Cook, veja aqui ) que sistema axiomático matemático é assumido?P=NPP=NP\mathbf{P} = \mathbf{NP}P≠NPP≠NP\mathbf{P} \neq \mathbf{NP} Para provar ou refutar tais declarações, você precisa assumir alguns...
Quais são os exemplos de problemas conhecidos em AMAM\mathsf{AM} (resp. MAMA\mathsf{MA} ) que não são conhecidos em NPNP\mathsf{NP} nem em BPPBPP\mathsf{BPP} ? Para AMAM\mathsf{AM} , eu sei que os dois exemplos a seguir: Não isomorfismo de gráfico: dados dois gráficos marcados GGG e HHH , eles...
Digamos que você tenha um número de conjuntos de números inteiros ( ), e pretende calcular interseções de alguns deles ( ∩ S 1 , S 3 , S 7 pode ser uma consulta, mas você quer para suportar muitas dessas consultas, ou talvez até todas as consultas possíveis)S1, S2. . . SnS1,S2...SnS_1, S_2 ... S_n∩...
Dado um número algébrico , estou interessado em encontrar uma aproximação de até uma determinada precisão, em que se refere à parte real do número complexo.αα\alphaR(eα)ℜ(eα)\Re(e^\alpha)R()ℜ()\Re() Formalmente, quero calcular um número racional rrr tal que
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...
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...
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 é...
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...
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 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 $...
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...
\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) É...
É comum definir a completude de em relação às reduções de numerosas uma no espaço de log.PPP Estou procurando uma classe de complexidade modo que haja problemas de P- completos com reduções de C de muitos um .C⊆LC⊆LC \subseteq \mathsf{L}PP\mathsf{P}CCC Qual é a menor classe de redução conhecida...
No artigo 'Sobre o desaparecimento dos coeficientes de Kronecker', aqui em http://arxiv.org/pdf/1507.02955v1.pdf , é mostrado que decidir a positividade dos coeficientes de Kronecker é geralmente difícil para o NP. No entanto, existe uma ressalva que afirma que apenas a positividade dos...
Em [1] afirma-se que "Continua sendo uma questão em aberto se todas as funções em possuem circuitos T C 0 (embora seja pelo menos sabido que nem todas as funções # P possuem circuitos T C 0 uniformes para DLogTime )."#P#P\#PTC0TC0TC^0#P#P\#PTC0TC0TC^0 circuitos gerados por funções dlogtime...
O Isomorfismo conjectura de Berman e Hartmanis afirma que todos conjuntos são -completo tempo polinomial isomorfo para o outro. Isto significa que N P problemas -Complete são eficientemente redutível para o outro através de calculável tempo polinomial e bijeções inversíveis. A conjectura implica P...