11 relações: Christos Papadimitriou, Complexidade computacional, Corolário, Digital object identifier, Grafo orientado, Linguagem de programação, Máquina de Turing não determinística, P versus NP, Recursividade (ciência da computação), Teorema de Immerman–Szelepcsényi, Walter Savitch.
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!!: Teorema de Savitch e Christos Papadimitriou · 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!!: Teorema de Savitch e Complexidade computacional · Veja mais »
Corolário
Um corolário (do latim tardio corollarĭum) é uma afirmação deduzida de uma verdade já demonstrada.
Novo!!: Teorema de Savitch e Corolário · Veja mais »
Digital object identifier
Digital object identifier (DOI) é um padrão para identificação de documentos em redes de computadores, como a Internet.
Novo!!: Teorema de Savitch e Digital object identifier · Veja mais »
Grafo orientado
Um grafo orientado (direcionado). Um grafo orientado, grafo dirigido, grafo direcionado ou digrafo é um par G.
Novo!!: Teorema de Savitch e Grafo orientado · Veja mais »
Linguagem de programação
C. A linguagem de programação é um método padronizado, formado por um conjunto de regras sintáticas e semânticas, de implementação de um código fonte - que pode ser compilado e transformado em um programa de computador, ou usado como script interpretado - que informará instruções de processamento ao computador.
Novo!!: Teorema de Savitch e Linguagem de programação · 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!!: Teorema de Savitch e Máquina de Turing não determinística · Veja mais »
P versus NP
O problema "P versus NP" é o principal problema aberto da Ciência da Computação.
Novo!!: Teorema de Savitch e P versus NP · Veja mais »
Recursividade (ciência da computação)
Em ciência da computação, a recursividade é a definição de uma sub-rotina (função ou método) que pode invocar a si mesma.
Novo!!: Teorema de Savitch e Recursividade (ciência da computação) · 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!!: Teorema de Savitch e Teorema de Immerman–Szelepcsényi · Veja mais »
Walter Savitch
Walter John Savitch é comumente conhecido por descobrir a classe de complexidade NL (espaço logarítmico não-determinístico), e pelo Teorema de Savitch que define uma relação entre as classes de complexidade NSPACE e DSPACE.