Acesso mais rápido do que o navegador!
13 relações: Algoritmo, BPP, Classe de complexidade, Co-NP, Complexidade computacional, Independência (estatística), Linguagem recursiva, Máquina de Turing não determinística, Máquina de Turing probabilística, NP (complexidade), P (complexidade), P versus NP, ZPP.
Algoritmo
Uma animação do algoritmo de ordenação quicksort de uma matriz de valores ao acaso. As barras vermelhas marcam o elemento pivô. No início da animação, estando o elemento para o lado direito, é escolhido como o pivô Em matemática e ciência da computação, um algoritmo é uma sequência finita de ações executáveis que visam obter uma solução para um determinado tipo de problema.
Novo!!: RP (complexidade computacional) e Algoritmo · 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!!: RP (complexidade computacional) e BPP · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: RP (complexidade computacional) e Classe de complexidade · Veja mais »
Co-NP
Na Teoria da complexidade, co-NP é uma Classe de complexidade.
Novo!!: RP (complexidade computacional) 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!!: RP (complexidade computacional) e Complexidade computacional · Veja mais »
Independência (estatística)
Em probabilidade e estatística, independência entre variáveis aleatórias ou eventos significa que a partir do resultado de um deles não é possível inferir nenhuma conclusão sobre o outro.
Novo!!: RP (complexidade computacional) e Independência (estatística) · Veja mais »
Linguagem recursiva
A linguagem recursiva em matemática, lógica e ciência da computação, uma linguagem formal (a definir de sequências finitas de símbolos tomados de um fixo alfabeto) é chamada recursiva se é um subconjunto recursivo no conjunto de todas as palavras possíveis sobre o alfabeto da linguagem.
Novo!!: RP (complexidade computacional) e Linguagem recursiva · 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!!: RP (complexidade computacional) 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!!: RP (complexidade computacional) e Máquina de Turing probabilística · 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!!: RP (complexidade computacional) 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!!: RP (complexidade computacional) e P (complexidade) · Veja mais »
P versus NP
O problema "P versus NP" é o principal problema aberto da Ciência da Computação.
Novo!!: RP (complexidade computacional) e P versus NP · 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.
