21 relações: Algoritmo, Árvore (grafo), BPP, Complexidade computacional, Complexidade de circuitos, Complexidade NL, Conjunto, Função exponencial dupla, Grafos acíclicos dirigidos, Hierarquia polinomial, LSPACE, Máquina oráculo, Número natural, NC (complexidade), NEXPTIME, NP (complexidade), NP-completo, P (complexidade), Problema da parada, PSPACE, RP (complexidade computacional).
Algoritmo
Uma animação do algoritmo de ordenação quicksort de uma matriz de valores ao acaso. As barras vermelhas marcam o elemento pivô. No início da animação, estando o elemento para o lado direito, é escolhido como o pivô Em matemática e ciência da computação, um algoritmo é uma sequência finita de ações executáveis que visam obter uma solução para um determinado tipo de problema.
Novo!!: Circuitos e conjuntos de números naturais e Algoritmo · Veja mais »
Árvore (grafo)
Na teoria dos grafos, uma árvore é um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos).
Novo!!: Circuitos e conjuntos de números naturais e Árvore (grafo) · Veja mais »
BPP
Na teoria da complexidade computacional, BPP (inglês: Bounded-error Probabilistic Polinomial time, probabilístico de tempo polinomial comprometido à erros) é a classe de problemas de decisão solúveis por uma Máquina de Turing em tempo polinomial, com uma probabilidade de erro de no máximo 1/3 para todas as instâncias.
Novo!!: Circuitos e conjuntos de números naturais e BPP · 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!!: Circuitos e conjuntos de números naturais e Complexidade computacional · Veja mais »
Complexidade de circuitos
No ramo da Ciência da computação teórica, complexidade de circuitos é um ramo da Teoria da complexidade computacional onde Função booleanas são classificadas de acordo com o tamanho ou o grau dos Circuitos booleanos que as computam.
Novo!!: Circuitos e conjuntos de números naturais e Complexidade de circuitos · 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!!: Circuitos e conjuntos de números naturais e Complexidade NL · Veja mais »
Conjunto
Conjunto é um conceito-chave primitivo do ramo matemático da Teoria dos Conjuntos.
Novo!!: Circuitos e conjuntos de números naturais e Conjunto · Veja mais »
Função exponencial dupla
Uma função exponencial dupla (curva vermelha) comparada a uma função exponencial (curva azul). Função exponencial dupla é uma constante matemática elevado à potência de uma função exponencial.
Novo!!: Circuitos e conjuntos de números naturais e Função exponencial dupla · Veja mais »
Grafos acíclicos dirigidos
Em matemática, um grafo acíclico dirigido, (em inglês: directed acyclic graph, ou simplesmente um dag ou DAG), é um grafo dirigido sem ciclo; isto é, para qualquer vértice v, não há nenhuma ligação dirigida começando e acabando em v. Estes grafos aparecem em modelos onde não faz sentido que um vértice tenha uma ligação com si próprio.
Novo!!: Circuitos e conjuntos de números naturais e Grafos acíclicos dirigidos · Veja mais »
Hierarquia polinomial
No ramo da Complexidade computacional a hierarquia polinomial é a hierarquia das Classes de complexidade que generaliza as classes P, NP e Co-NP para Máquinas oráculo.
Novo!!: Circuitos e conjuntos de números naturais e Hierarquia polinomial · Veja mais »
LSPACE
Em teoria da complexidade, L (também conhecido como LSPACE ou DLOGSPACE) é a classe de complexidade que contém problemas de decisão os quais podem ser resolvidos por uma máquina de Turing utilizando uma quantidade de espaço de memória logarítmico.
Novo!!: Circuitos e conjuntos de números naturais e LSPACE · Veja mais »
Máquina oráculo
Em teoria da computação, uma máquina oráculo é uma máquina abstrata usada para estudar problemas de decisão.
Novo!!: Circuitos e conjuntos de números naturais e Máquina oráculo · Veja mais »
Número natural
Um número natural é um número inteiro não negativo \. Em alguns contextos, número natural é definido como um número inteiro positivo, sendo também o zero considerado como um número natural (mesmo não sendo positivo e sim nulo/neutro): \. O conjunto dos números naturais é, comumente, denotado pelo símbolo \mathbb.
Novo!!: Circuitos e conjuntos de números naturais e Número natural · Veja mais »
NC (complexidade)
Na teoria da complexidade, a classe NC (para "Classe de Nick") é o conjunto de Problema de decisão decidíveis em tempo polilogarítmico em um computador paralelo com um número polinomial de processadores.
Novo!!: Circuitos e conjuntos de números naturais e NC (complexidade) · Veja mais »
NEXPTIME
Em teoria da complexidade, NEXPSPACE (também chamada de NEXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing não determinística em espaço O(2p(n)) para uma dada p(n) e espaço ilimitado.
Novo!!: Circuitos e conjuntos de números naturais e NEXPTIME · 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!!: Circuitos e conjuntos de números naturais e NP (complexidade) · Veja mais »
NP-completo
Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo.
Novo!!: Circuitos e conjuntos de números naturais e NP-completo · 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!!: Circuitos e conjuntos de números naturais e P (complexidade) · 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!!: Circuitos e conjuntos de números naturais e Problema da parada · 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!!: Circuitos e conjuntos de números naturais e PSPACE · Veja mais »
RP (complexidade computacional)
Tempo Polinomial Aleatorizado (em inglês, Randomized polynomial time: RP) é uma classe de complexidade da complexidade computacional, problemas para nos quais a Máquina de Turing probabilística possui as seguintes propriedades.
Novo!!: Circuitos e conjuntos de números naturais e RP (complexidade computacional) · Veja mais »