19 relações: Association for Computing Machinery, BPP, BQP, Classe de complexidade, Co-NP, Complexidade computacional, Computador quântico, Hierarquia polinomial, Larry Stockmeyer, Lógica de segunda ordem, Máquina de Turing, Máquina de Turing alternada, Máquina oráculo, NP (complexidade), P (complexidade), PP (complexidade), PSPACE, RP (complexidade computacional), Springer Science+Business Media.
Association for Computing Machinery
A Association for Computing Machinery (ACM; lit. Associação para Maquinaria da Computação) foi fundada em 1947 como a primeira sociedade científica e educacional dedicada à computação.
Novo!!: PH (complexidade) e Association for Computing Machinery · Veja mais »
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!!: PH (complexidade) e BPP · Veja mais »
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!!: PH (complexidade) e BQP · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: PH (complexidade) e Classe de complexidade · Veja mais »
Co-NP
Na Teoria da complexidade, co-NP é uma Classe de complexidade.
Novo!!: PH (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!!: PH (complexidade) e Complexidade computacional · Veja mais »
Computador quântico
A esfera de Bloch é uma representação de um qubit, o bloco de construção fundamental de computadores quânticos. Um computador quântico é um dispositivo que executa cálculos fazendo uso direto de propriedades da mecânica quântica, tais como sobreposição e interferência.
Novo!!: PH (complexidade) e Computador quântico · 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!!: PH (complexidade) e Hierarquia polinomial · Veja mais »
Larry Stockmeyer
Larry Joseph Stockmeyer (–) foi um cientista da computação americano.
Novo!!: PH (complexidade) e Larry Stockmeyer · Veja mais »
Lógica de segunda ordem
Na lógica matemática, a lógica de segunda ordem é uma extensão da lógica de primeira ordem, onde a própria lógica de primeira ordem é uma extensão de lógica proposicional.
Novo!!: PH (complexidade) e Lógica de segunda ordem · Veja mais »
Máquina de Turing
Representação artística de uma máquina de Turing A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936).
Novo!!: PH (complexidade) e Máquina de Turing · Veja mais »
Máquina de Turing alternada
Em complexidade de computação teórica, uma máquina de Turing alternada (MTA) é uma máquina de Turing não-determinística (MTN) com a regra que aceita computações que generalizam regras usadas na definição da complexidade das classes NP e co-NP.
Novo!!: PH (complexidade) e Máquina de Turing alternada · 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!!: PH (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!!: PH (complexidade) e NP (complexidade) · 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!!: PH (complexidade) e P (complexidade) · Veja mais »
PP (complexidade)
Em Complexidade computacional, PP é a classe de problemas de decisão decidíveis por uma Máquina de Turing probabilística em tempo polinomial, com uma probabilidade de erro de menos do que 1/2 para todas as instâncias.
Novo!!: PH (complexidade) e PP (complexidade) · 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!!: PH (complexidade) e PSPACE · 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!!: PH (complexidade) e RP (complexidade computacional) · Veja mais »
Springer Science+Business Media
Springer Science+Business Media ou Springer-Verlag, ou ainda, simplesmente Springer é uma editora mundial baseada na Alemanha, a qual publica livros-texto, livros de referência acadêmica, e periódicos de artigos com revisão por pares (peer-review), com foco em ciência, tecnologia, matemática, e medicina.
Novo!!: PH (complexidade) e Springer Science+Business Media · Veja mais »