Acesso mais rápido do que o navegador!
16 relações: Algoritmo probabilístico, Autômato com pilha determinístico, BPL (complexidade), Classe de complexidade, Complexidade computacional, Complexidade NL, Conectividade st, Grande-O, Linguagem livre de contexto, Linguagem livre de contexto determinística, Máquina de Turing, Máquina de Turing probabilística, P (complexidade), RL (complexidade), Stephen Cook, Teorema de Savitch.
Algoritmo probabilístico
Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica.
Novo!!: SC (complexidade) e Algoritmo probabilístico · Veja mais »
Autômato com pilha determinístico
Na teoria dos autômatos, um autômato com pilha determinístico (APD) é uma variante de autômato com pilha.
Novo!!: SC (complexidade) e Autômato com pilha determinístico · Veja mais »
BPL (complexidade)
Na teoria da complexidade computacional, BPL (Bounded-error Probabilistic Logarithmic-space, i.e. Espaço Logarítmico Probabilístico de Erro Limitado), às vezes chamada de BPLP (Espaço Logarítmico Probabilístico de Erro Limitado e Tempo Polinomial), é a classe de complexidade dos problemas solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro bilateral.
Novo!!: SC (complexidade) e BPL (complexidade) · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: SC (complexidade) e Classe de complexidade · 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!!: SC (complexidade) e Complexidade computacional · Veja mais »
Complexidade NL
Na teoria da complexidade, NL (espaço-logarítmico não-determinístico) é a classe de complexidade contendo problemas de decisão que podem ser resolvidos por uma máquina de Turing não-determinística, usando uma quantidade de espaço de memória logarítmica.
Novo!!: SC (complexidade) e Complexidade NL · Veja mais »
Conectividade st
Em ciência da computação e teoria da complexidade computacional, conectividade st é um problema de decisão onde dados os vértices s e t de um grafo direcionado, questiona-se se t é acessível partindo de s. Formalmente, o problema de decisão é dada por.
Novo!!: SC (complexidade) e Conectividade st · Veja mais »
Grande-O
''g''(''x'') sempre que ''x'' ≥ ''x''0. Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples.
Novo!!: SC (complexidade) e Grande-O · Veja mais »
Linguagem livre de contexto
Na teoria de linguagens formais, uma linguagem livre de contexto (LLC) é uma linguagem gerada por alguma gramática livre de contexto (GLC).
Novo!!: SC (complexidade) e Linguagem livre de contexto · Veja mais »
Linguagem livre de contexto determinística
Na teoria da linguagem formal, linguagens livres de contexto determinísticas (LLCD) são um subconjunto de linguagens livres de contexto (LLC).
Novo!!: SC (complexidade) e Linguagem livre de contexto determinística · 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!!: SC (complexidade) e Máquina de Turing · 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!!: SC (complexidade) e Máquina de Turing probabilística · 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!!: SC (complexidade) e P (complexidade) · Veja mais »
RL (complexidade)
Espaço Logarítmico Randomizado (RL), às vezes chamado de RLP (Espaço Logarítmico Randomizado de tempo Polinomial), é a classe de complexidade de problemas da teoria da complexidade computacional solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro unilateral.
Novo!!: SC (complexidade) e RL (complexidade) · Veja mais »
Stephen Cook
Stephen Arthur Cook, (Buffalo) é um cientista da computação e matemático estadunidense-canadense, que teve maior contribuição no campo da teoria da complexidade e complexidade de prova.
Novo!!: SC (complexidade) e Stephen Cook · Veja mais »
Teorema de Savitch
Na teoria da complexidade computacional, o teorema de Savitch, provado por Walter Savitch em 1970, afirma que para toda função ƒ(n) ≥ log(n), em outras palavras, se uma máquina de Turing não-determinística pode resolver um problema usando um espaço f(n) (polinomial), uma máquina de Turing determinística ordinária pode resolver o mesmo problema dentro dessa região delimitada.
Novo!!: SC (complexidade) e Teorema de Savitch · Veja mais »
