Acesso mais rápido do que o navegador!
26 relações: Classe de complexidade, Complexidade computacional, Conjunto diofantino, Conjunto finito, Conjuntos criativos e produtivos, Conjuntos recursivamente enumeráveis, Equação diofantina, Função computável, Gramática formal, Gramática irrestrita, Grupo (matemática), John Myhill, Lógica de primeira ordem, Linguagem recursiva, Lista de problemas indecidíveis, Máquina de Turing, Problema da correspondência de Post, Problema da palavra para grupos, Problema da parada, Problema de decisão, Redução por mapeamento, Semigrupo, Subconjunto, Teorema de Rice, Teoria da computabilidade, Validade.
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: RE (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!!: RE (complexidade) e Complexidade computacional · Veja mais »
Conjunto diofantino
Na matemática, uma Equação diofantina é uma equação da forma P(x1,..., xj, y1,..., yk).
Novo!!: RE (complexidade) e Conjunto diofantino · Veja mais »
Conjunto finito
Intuitivamente, um conjunto é finito quando é possível contar seus elementos e a contagem termina.
Novo!!: RE (complexidade) e Conjunto finito · Veja mais »
Conjuntos criativos e produtivos
Em Teoria da Computabilidade, conjuntos produtivos e conjuntos criativos são tipos de conjuntos de números naturais que tem aplicações importantes em lógica matemática.
Novo!!: RE (complexidade) e Conjuntos criativos e produtivos · Veja mais »
Conjuntos recursivamente enumeráveis
Na Teoria da computabilidade, tradicionalmente chamada teoria da recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing-reconhecível se.
Novo!!: RE (complexidade) e Conjuntos recursivamente enumeráveis · Veja mais »
Equação diofantina
Na matemática, uma equação Diofantina é uma equação polinomial que permite a duas ou mais variáveis assumirem apenas valores inteiros.
Novo!!: RE (complexidade) e Equação diofantina · Veja mais »
Função computável
Funções computáveis são os objetos básicos de estudo na teoria da computabilidade.
Novo!!: RE (complexidade) e Função computável · Veja mais »
Gramática formal
Em teoria das linguagens formais, uma gramática formal (algumas vezes simplesmente chamada de gramática) é um conjunto de regras de produção de cadeias em uma linguagem formal, ou seja, um objeto que permite especificar uma linguagem ou língua.
Novo!!: RE (complexidade) e Gramática formal · Veja mais »
Gramática irrestrita
Em Teoria da computação, a Gramática irrestrita (conhecida também como Gramática com estrutura de frase) é também conhecida como Tipo 0 da Hierarquia de Chomsky, que são aquelas às quais nenhuma limitação é imposta.
Novo!!: RE (complexidade) e Gramática irrestrita · Veja mais »
Grupo (matemática)
A Vingança de Rubik (versão 4x4x4 do Cubo de Rubik) formam um grupo. Em matemática, um grupo é um conjunto de elementos associados a uma operação que combina dois elementos quaisquer para formar um terceiro.
Novo!!: RE (complexidade) e Grupo (matemática) · Veja mais »
John Myhill
John R. Myhill, Sr. (11 de agosto de 1923 – 15 de fevereiro de 1987) foi um matemático britânico.
Novo!!: RE (complexidade) e John Myhill · Veja mais »
Lógica de primeira ordem
A lógica de primeira ordem (LPO), conhecida também como cálculo de predicados de primeira ordem (CPPO), é um sistema lógico que estende a lógica proposicional (lógica sentencial) e que é estendida pela lógica de segunda ordem.
Novo!!: RE (complexidade) e Lógica de primeira ordem · 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!!: RE (complexidade) e Linguagem recursiva · Veja mais »
Lista de problemas indecidíveis
Em Teoria da Computabilidade, o Problema indecidível é um problema em que é impossível construir um algoritmo que sempre responde sim ou não, ele pode não responder ou responder errado.
Novo!!: RE (complexidade) e Lista de problemas indecidíveis · 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!!: RE (complexidade) e Máquina de Turing · Veja mais »
Problema da correspondência de Post
O problema da correspondência de Post é um problema de decisão indecidível que foi introduzido por Emil Post em 1946..
Novo!!: RE (complexidade) e Problema da correspondência de Post · Veja mais »
Problema da palavra para grupos
Na álgebra abstrata, o problema da palavra de um receptor recursivo na resolução de um algoritmo de nome grupo G, fornece um algoritmo de duas palavras para G, de forma que representem o mesmo elemento G. Apesar de ser dito popularmente como "Problema da palavra para grupos G" precisamente, ela é uma representação de um grupo que faz ou não faz soluções para esses tipos de problemas.
Novo!!: RE (complexidade) e Problema da palavra para grupos · Veja mais »
Problema da parada
Na teoria da computabilidade o experimento mental do problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma: Alan Turing provou em 1936 que um algoritmo genérico para resolver o problema da parada para todos pares programa-entrada possíveis não pode existir.
Novo!!: RE (complexidade) e Problema da parada · 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!!: RE (complexidade) e Problema de decisão · Veja mais »
Redução por mapeamento
Na teoria da computabilidade e teoria da complexidade computacional, uma redução por mapeamento é uma redução que converte instâncias de um problema de decisão em instâncias de um outro problema de decisão.
Novo!!: RE (complexidade) e Redução por mapeamento · Veja mais »
Semigrupo
Um semigrupo pode ser definido de 2 maneiras completamente equivalentes.
Novo!!: RE (complexidade) e Semigrupo · Veja mais »
Subconjunto
Diagrama de Euler ilustrando o fato de que A é subconjunto de B ou, equivalentemente, que B é superconjunto de A Em teoria dos conjuntos, quando todo elemento de um conjunto A é também elemento de um conjunto B, dizemos que A é um subconjunto de B, denotado A \subseteq B (também dito "A é uma parte de B" ou "A está contido em B").
Novo!!: RE (complexidade) e Subconjunto · Veja mais »
Teorema de Rice
Na teoria da computação, o teorema de Rice afirma que, para qualquer propriedade não-trivial de funções parciais, não existe um método geral e eficaz para decidir se um algoritmo calcula uma função parcial com essa propriedade.
Novo!!: RE (complexidade) e Teorema de Rice · Veja mais »
Teoria da computabilidade
A teoria da computabilidade, também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 1930 com o estudo das funções computáveis e do grau de Turing.
Novo!!: RE (complexidade) e Teoria da computabilidade · Veja mais »
Validade
O termo validade (também chamada verdade lógica, verdade analítica, ou verdade necessária), em lógica, refere-se geralmente a uma propriedade de enunciados particulares e de argumentos dedutivos.
Novo!!: RE (complexidade) e Validade · Veja mais »
