15 relações: Ciência da computação, Coloração de arestas, Complexidade computacional, David Stifler Johnson, Fatoração, Homomorfismo de grafos, Isomorfismo de grafos, Journal of the ACM, NP (complexidade), NP-completo, NP-difícil, P (complexidade), Problema da correspondência de Post, Programação linear, Teste de primalidade.
Ciência da computação
A Ciência da Computação lida com fundamentos teóricos da informação, computação, e técnicas práticas para suas implementações e aplicações.
Novo!!: Computers and Intractability e Ciência da computação · Veja mais »
Coloração de arestas
Em teoria dos grafos, uma coloração de arestas de um grafo é a atribuição de “cores” para as arestas de um grafo de forma que não haja duas arestas adjacentes tendo a mesma cor.
Novo!!: Computers and Intractability e Coloração de arestas · Veja mais »
Complexidade computacional
A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si.
Novo!!: Computers and Intractability e Complexidade computacional · Veja mais »
David Stifler Johnson
David Stifler Johnson (9 de dezembro de 1945 – 8 de março de 2016) foi um cientista da computação estadunidense especializado em algoritmos e otimização.
Novo!!: Computers and Intractability e David Stifler Johnson · Veja mais »
Fatoração
(AO 1945: Factorização) é o termo usado na álgebra para designar a decomposição que se faz de cada um dos elementos que integram um produto, ou seja, o resultado de uma multiplicação.
Novo!!: Computers and Intractability e Fatoração · Veja mais »
Homomorfismo de grafos
No campo da matemática da teoria dos grafos um homomorfismo de grafos é um mapeamento entre dois grafos que respeita suas estruturas.
Novo!!: Computers and Intractability e Homomorfismo de grafos · Veja mais »
Isomorfismo de grafos
Em teoria dos grafos, um isomorfismo dos grafos G e H é uma bijeção entre os conjuntos de vértices de G e H de tal forma que quaisquer dois vértices u e v de G são adjacentes em G se e somente se ƒ(u) e ƒ(v) são adjacentes em H. Este tipo de bijeção é comumente chamado de "bijeção com preservação de arestas", de acordo com a noção geral de isomorfismo sendo uma bijeção de preservação-de-estrutura.
Novo!!: Computers and Intractability e Isomorfismo de grafos · Veja mais »
Journal of the ACM
O Journal of the ACM (JACM) é a revista científica carro-chefe da Association for Computing Machinery (ACM).
Novo!!: Computers and Intractability e Journal of the ACM · Veja mais »
NP (complexidade)
Na teoria da complexidade computacional, NP é o acrônimo em inglês para Tempo polinomial não determinístico (Non-Deterministic Polynomial time) que denota o conjunto de problemas que são decidíveis em tempo polinomial por uma máquina de Turing não-determinística.
Novo!!: Computers and Intractability e NP (complexidade) · Veja mais »
NP-completo
Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo.
Novo!!: Computers and Intractability e NP-completo · Veja mais »
NP-difícil
NP-difícil (ou NP-hard, ou NP-complexo) na teoria da complexidade computacional, é uma classe de problemas que são, informalmente, "Pelo menos tão difíceis quanto os problemas mais difíceis em NP".
Novo!!: Computers and Intractability e NP-difícil · Veja mais »
P (complexidade)
Na teoria da complexidade computacional, P é o acrônimo em inglês para Tempo polinomial determinístico (Deterministic Polynomial time) que denota o conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística.
Novo!!: Computers and Intractability e P (complexidade) · Veja mais »
Problema da correspondência de Post
O problema da correspondência de Post é um problema de decisão indecidível que foi introduzido por Emil Post em 1946..
Novo!!: Computers and Intractability e Problema da correspondência de Post · Veja mais »
Programação linear
Exemplo de poliedro (bidimensional) resultante das condições de um problema de programação linear. Em matemática, problemas de Programação Linear (PL) são problemas de optimização nos quais a função objetivo e as restrições são todas lineares.
Novo!!: Computers and Intractability e Programação linear · Veja mais »
Teste de primalidade
Um teste de primalidade é um algoritmo para determinar se um dado número inteiro é primo.
Novo!!: Computers and Intractability e Teste de primalidade · Veja mais »