Acesso mais rápido do que o navegador!
12 relações: BPP, Classe de complexidade, Co-NP, Complexidade computacional, Máquina oráculo, NP (complexidade), NP-completo, NP-difícil, Problema computacional, Redução (complexidade), RP (complexidade computacional), ZPP.
BPP
Na teoria da complexidade computacional, BPP (inglês: Bounded-error Probabilistic Polinomial time, probabilístico de tempo polinomial comprometido à erros) é a classe de problemas de decisão solúveis por uma Máquina de Turing em tempo polinomial, com uma probabilidade de erro de no máximo 1/3 para todas as instâncias.
Novo!!: Completo (complexidade) e BPP · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: Completo (complexidade) e Classe de complexidade · Veja mais »
Co-NP
Na Teoria da complexidade, co-NP é uma Classe de complexidade.
Novo!!: Completo (complexidade) e Co-NP · 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!!: Completo (complexidade) e Complexidade computacional · Veja mais »
Máquina oráculo
Em teoria da computação, uma máquina oráculo é uma máquina abstrata usada para estudar problemas de decisão.
Novo!!: Completo (complexidade) e Máquina oráculo · 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!!: Completo (complexidade) 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!!: Completo (complexidade) 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!!: Completo (complexidade) e NP-difícil · Veja mais »
Problema computacional
Na ciência da teoria da computação, um problema computacional é um objeto matemático que representa um coleção de questões que computadores talvez queiram resolver.
Novo!!: Completo (complexidade) e Problema computacional · Veja mais »
Redução (complexidade)
Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro.
Novo!!: Completo (complexidade) e Redução (complexidade) · Veja mais »
RP (complexidade computacional)
Tempo Polinomial Aleatorizado (em inglês, Randomized polynomial time: RP) é uma classe de complexidade da complexidade computacional, problemas para nos quais a Máquina de Turing probabilística possui as seguintes propriedades.
Novo!!: Completo (complexidade) e RP (complexidade computacional) · Veja mais »
ZPP
Na Teoria da complexidade computacional, ZPP (inglês: Zero-error Probabilistic Polinomial time, Probalístico de tempo polinominal sem erros) é a classe complexa de problemas em que uma Máquina de Turing existe com estas propriedades.
Novo!!: Completo (complexidade) e ZPP · Veja mais »
