Acesso mais rápido do que o navegador!
16 relações: Énuplo, Christos Papadimitriou, Classe de complexidade, Co-NP, Complexidade computacional, EXPSPACE, Exptime, Função construível, Larry Stockmeyer, Linguagem formal, Máquina de Turing não determinística, Michael Sipser, NP (complexidade), P (complexidade), PSPACE, Tese da computação paralela.
Énuplo
Énuplo (também conhecido como ênuplo, énupla, ênupla, n-tuplo, n-upla ou simplesmente tupla) é uma sequência ordenada de n elementos, que pode ser definida pela recursão do par ordenado.
Novo!!: Máquina de Turing alternante e Énuplo · Veja mais »
Christos Papadimitriou
Christos Harilaos Papadimitriou (em grego: Χρήστος ΧαριλάουΠαπαδημητρίου; Atenas) é um Cientista da Computação da divisão de Ciência da Computação da Universidade da Califórnia em Berkeley, Estados Unidos.
Novo!!: Máquina de Turing alternante e Christos Papadimitriou · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: Máquina de Turing alternante e Classe de complexidade · Veja mais »
Co-NP
Na Teoria da complexidade, co-NP é uma Classe de complexidade.
Novo!!: Máquina de Turing alternante 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!!: Máquina de Turing alternante e Complexidade computacional · 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!!: Máquina de Turing alternante e EXPSPACE · 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!!: Máquina de Turing alternante e Exptime · Veja mais »
Função construível
Na teoria da complexidade, uma função tempo-construível é uma função f dos números naturais para números naturais com a propriedade de que f(n) pode ser construída a partir de n por uma máquina de Turing em tempo de ordem f(n).
Novo!!: Máquina de Turing alternante e Função construível · Veja mais »
Larry Stockmeyer
Larry Joseph Stockmeyer (–) foi um cientista da computação americano.
Novo!!: Máquina de Turing alternante e Larry Stockmeyer · Veja mais »
Linguagem formal
Entende-se por linguagem formal estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter-relacionamentos.
Novo!!: Máquina de Turing alternante e Linguagem formal · 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!!: Máquina de Turing alternante 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!!: Máquina de Turing alternante e Michael Sipser · 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!!: Máquina de Turing alternante 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!!: Máquina de Turing alternante e P (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!!: Máquina de Turing alternante e PSPACE · Veja mais »
Tese da computação paralela
Na teoria da complexidade computacional, a tese da computação paralela é uma hipótese que afirma que o tempo é utilizado por uma máquina paralela (razoável) e é polinomialmente relacionada com o espaço utilizado por uma máquina seqüencial.
Novo!!: Máquina de Turing alternante e Tese da computação paralela · Veja mais »
