Acesso mais rápido do que o navegador!
13 relações: Complexidade de caso genérico, E (complexidade), FP (Complexidade), Linguagem esparsa, NP-completo, P-Sharp completude, P/polinomial, PPA (complexidade), PPP (complexidade), Problema de função, Problema de isomorfismo de grafos, Redução linear, Redução PTAS.
Complexidade de caso genérico
Complexidade de Caso Genérico é uma subárea da teoria da complexidade computacional que estuda a complexidade de problemas computacionais na "maioria das entradas".
Novo!!: Redução em tempo polinomial e Complexidade de caso genérico · Veja mais »
E (complexidade)
Na teoria da complexidade computacional, a Classe de complexidade E é o conjunto de problemas de decisão que podem ser resolvidos por uma máquina de Turing determinística em tempo 2O(n) e, portanto, é igual à classe de complexidade DTIME(2O(n)).
Novo!!: Redução em tempo polinomial e E (complexidade) · Veja mais »
FP (Complexidade)
Na teoria da complexidade computacional, a complexidade de classe FP é o conjunto de problemas de função que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial; é a versão funcional da classe P de problemas de decisão .
Novo!!: Redução em tempo polinomial e FP (Complexidade) · Veja mais »
Linguagem esparsa
Em teoria da complexidade computacional, uma linguagem esparsa é uma linguagem formal (um conjunto de strings) cujo número de strings de comprimento n na língua é limitada por uma função de polinômio n. São utilizadas principalmente no estudo da relação entre a classe de complexidade NP com outras classes.
Novo!!: Redução em tempo polinomial e Linguagem esparsa · 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!!: Redução em tempo polinomial e NP-completo · Veja mais »
P-Sharp completude
#P-completo, pronunciado "P-sharp completo" ou "P-número completo" é uma classe de complexidade na teoria da complexidade computacional.
Novo!!: Redução em tempo polinomial e P-Sharp completude · Veja mais »
P/polinomial
Na Teoria da complexidade computacional, P/poly é a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma máquina de Turing com um polynomial-bounded advice function.
Novo!!: Redução em tempo polinomial e P/polinomial · Veja mais »
PPA (complexidade)
PPA é uma classe de complexidade, significando em inglês "Polynomial Parity Argument" (Argumento de Paridade Polinomial).
Novo!!: Redução em tempo polinomial e PPA (complexidade) · Veja mais »
PPP (complexidade)
PPP é uma classe de complexidade, abreviação de "Princípio Polinomial da Casa de Pombos".
Novo!!: Redução em tempo polinomial e PPP (complexidade) · Veja mais »
Problema de função
Em teoria da complexidade computacional, um problema de função é um problema computacional onde uma única saída (de uma função total) é esperada pra cada entrada, mas a sáida é mais complexa do que um problema de decisão, isto é, não é apenas SIM ou NÃO.
Novo!!: Redução em tempo polinomial e Problema de função · Veja mais »
Problema de isomorfismo de grafos
O problema de isomorfismo de grafos é um problema computacional para determinar se dois grafos finitos são isomórficos.
Novo!!: Redução em tempo polinomial e Problema de isomorfismo de grafos · Veja mais »
Redução linear
Em Ciência da Computação, em particular no estudo de algoritmos de aproximação, uma L-redução ("redução linear") é uma transformação de problemas de otimização que linearmente preservam características de aproximação.
Novo!!: Redução em tempo polinomial e Redução linear · Veja mais »
Redução PTAS
Na teoria de complexidade computacional, uma redução PTAS é uma redução com preservação de aproximação que é geralmente usada para fazer reduções junto à soluções para problemas de otimização.
Novo!!: Redução em tempo polinomial e Redução PTAS · Veja mais »
