Acesso mais rápido do que o navegador!
14 relações: Classe de complexidade, Complexidade computacional, Complexidade NL, DSPACE, Dtime, EXPSPACE, Linguagem regular, Linguagem sensível ao contexto, Máquina de Turing não determinística, Michael Sipser, Problema de decisão, PSPACE, Teorema de Immerman–Szelepcsényi, Teorema de Savitch.
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: NSPACE 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!!: NSPACE 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!!: NSPACE e Complexidade NL · Veja mais »
DSPACE
Em complexidade computacional, DSPACE ou simplesmente SPACE é um recurso computacional descrevendo a disponibilidade de memória para uma máquina de Turing.
Novo!!: NSPACE e DSPACE · Veja mais »
Dtime
Na teoria da complexidade computacional, DTIME (ou TIME) é o recurso computacional de tempo de computação para uma máquina de Turing determinística.
Novo!!: NSPACE e Dtime · Veja mais »
EXPSPACE
Em teoria da complexidade computacionais, EXPSPACE é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em espaço O(2p(n)) onde p(n) é uma função polinomial de n. (Alguns autores restringem p(n) para uma função linear, mas a maioria chama a classe resultante de ESPACE.) Se, por outro lado, nós usamos uma máquina não determinísitica, teremos a classe NEXPSPACE, que é igual a EXPSPACE pelo teorema de savitch.
Novo!!: NSPACE e EXPSPACE · Veja mais »
Linguagem regular
Na teoria da ciência da computação e teoria formal de linguagem, uma linguagem regular é uma linguagem formal que pode ser expressa usando expressões regulares, ou seja, uma linguagem produzida utilizando as operações de concatenação, união e fecho de Kleene sobre os elementos de um alfabeto.
Novo!!: NSPACE e Linguagem regular · Veja mais »
Linguagem sensível ao contexto
Na Ciência da computação teórica, a 'linguagem sensível ao contexto' é uma linguagem formal que pode ser definida por uma Gramática sensível ao contexto.
Novo!!: NSPACE e Linguagem sensível ao contexto · 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!!: NSPACE e Máquina de Turing não determinística · Veja mais »
Michael Sipser
Michael Fredric Sipser é um professor de Matemática Aplicada no grupo de teoria da computação do Massachusetts Institute of Technology.
Novo!!: NSPACE e Michael Sipser · Veja mais »
Problema de decisão
Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não.
Novo!!: NSPACE e Problema de decisão · 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!!: NSPACE e PSPACE · Veja mais »
Teorema de Immerman–Szelepcsényi
Na teoria de complexidade computacional, o teorema de Immerman–Szelepcsényi foi provado de forma independente por Neil Immerman e Róbert Szelepcsényi no ano de 1987.
Novo!!: NSPACE e Teorema de Immerman–Szelepcsényi · 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!!: NSPACE e Teorema de Savitch · Veja mais »
