Acesso mais rápido do que o navegador!
14 relações: BQP, Complexidade computacional, Diferença simétrica, Hierarquia polinomial, Lista de problemas em aberto, Low, Máquina de Turing não determinística, Máquina de Turing probabilística, Máquina oráculo, NP-completo, PostBQP, PSPACE, QMA, União (matemática).
BQP
A relação suspeita entre '''BQP''' para outros espaços de problemasMichael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. Em Teoria da Complexidade Computacional, BQP (do inglês bounded error quantum polynomial time) é a classe de problemas de decisão solúveis por um computador quântico em tempo polinomial, com uma probabilidade de erro de até 1/3 para todas as instâncias.
Novo!!: PP (complexidade) e BQP · 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!!: PP (complexidade) e Complexidade computacional · Veja mais »
Diferença simétrica
Em matemática, a diferença simétrica de dois conjuntos é o conjunto de elementos que estão em um dos conjuntos, e não em sua interseção.
Novo!!: PP (complexidade) e Diferença simétrica · Veja mais »
Hierarquia polinomial
No ramo da Complexidade computacional a hierarquia polinomial é a hierarquia das Classes de complexidade que generaliza as classes P, NP e Co-NP para Máquinas oráculo.
Novo!!: PP (complexidade) e Hierarquia polinomial · Veja mais »
Lista de problemas em aberto
Segue a lista de alguns problemas em aberto dividida nas seguintes categorias.
Novo!!: PP (complexidade) e Lista de problemas em aberto · Veja mais »
Low
Sem descrição
Novo!!: PP (complexidade) e Low · Veja mais »
Máquina de Turing não determinística
Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.
Novo!!: PP (complexidade) e Máquina de Turing não determinística · Veja mais »
Máquina de Turing probabilística
Em Teoria da Computabilidade, uma máquina de Turing probabilística é uma Máquina de Turing não determinística que escolhe aleatoriamente dentre as transições a cada ponto, de acordo com alguma distribuição de probabilidade.
Novo!!: PP (complexidade) e Máquina de Turing probabilística · 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!!: PP (complexidade) e Máquina oráculo · 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!!: PP (complexidade) e NP-completo · Veja mais »
PostBQP
Em teoria da complexidade computacional, PostBQP é uma classe de complexidade que consiste de todos os problemas computacionais solúveis em tempo polinomial em uma Máquina de Turing quântica com pós-seleção e erro limitado (no sentido de que o algoritmo é correto ao menos em 2/3 das vezes para todas as entradas).
Novo!!: PP (complexidade) e PostBQP · Veja mais »
PSPACE
Na teoria da complexidade computacional, PSPACE é o conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço.
Novo!!: PP (complexidade) e PSPACE · Veja mais »
QMA
QMA, na teoria da complexidade, que vem de Quantum Merlin Arthur, é uma classe de complexidade análoga à classe NP ou à classe de complexidade probabilística MA.
Novo!!: PP (complexidade) e QMA · Veja mais »
União (matemática)
Indicação da união entre os conjuntos A e B Em teoria dos conjuntos, a união de dois ou mais conjuntos é o conjunto dos elementos que pertencem a pelo menos um destes conjuntos.
Novo!!: PP (complexidade) e União (matemática) · Veja mais »
