Logotipo
Unionpédia
Comunicação
Disponível no Google Play
Novo! Faça o download do Unionpédia em seu dispositivo Android™!
Livre
Acesso mais rápido do que o navegador!
E sem anúncios!

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.

9 relações: Algoritmo Las Vegas, Algoritmo probabilístico, BPP, BQP, Complexidade computacional, Computador quântico, Exptime, Máquina de Turing, P (complexidade).

Algoritmo Las Vegas

Em computação, um algoritmo Las Vegas é um algoritmo randômico que sempre retorna resultados corretos; isto é, ele sempre produz o resultado correto ou informa sobre a falha.

Novo!!: ZPP e Algoritmo Las Vegas · Veja mais »

Algoritmo probabilístico

Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica.

Novo!!: ZPP e Algoritmo probabilístico · 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!!: ZPP e BPP · Veja mais »

BQP

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!!: ZPP 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!!: ZPP e Complexidade computacional · Veja mais »

Computador quântico

A Esfera de Block é 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!!: ZPP e Computador quântico · Veja mais »

Exptime

Na teoria da complexidade computacional, a classe de complexidade Exptime (às vezes chamado EXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em O(2p(n)) tempo, onde p (n) é uma função polinomial de n. Em termos de DTIME, Sabemos que e também, pelo time hierarchy theoremeo space hierarchy theorem, que assim pelo menos uma das três primeiras inclusões e pelo menos uma das três últimas inclusões deve ser adequada, mas não se sabe quais são.

Novo!!: ZPP e Exptime · 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!!: ZPP e Máquina de Turing · 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!!: ZPP e P (complexidade) · Veja mais »

Redireciona aqui:

Zpp.

CessanteEntrada
Ei! Agora estamos em Facebook! »