30 relações: Algoritmo, Avi Wigderson, Árvore de extensão, Árvore de extensão mínima, Busca em largura, Busca em profundidade, Classe de complexidade, Coloração de grafos, Complemento (complexidade), Complexidade computacional, Complexidade NL, Conectividade st, Endre Szemerédi, Grafo bipartido, Grafo orientado, Journal of the ACM, L/Poly, LSPACE, Máquina de Turing, Máquina oráculo, Máquinas de Turing Simétricas, Omer Reingold, Ou exclusivo, Palavra de aviso, Problema de satisfatibilidade booliana, Redução em espaço logarítmico, RL (complexidade), Se e somente se, Teorema de Savitch, Teoria dos grafos.
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!!: Complexidade SL e Algoritmo · Veja mais »
Avi Wigderson
Avi Wigderson (אבי ויגדרזון) é um matemático e informático israelense.
Novo!!: Complexidade SL e Avi Wigderson · Veja mais »
Árvore de extensão
Uma árvore de extensão ou árvore de dispersão (spanning tree) é o subconjunto de arestas de um grafo que forma uma árvore contendo todos os vértices.
Novo!!: Complexidade SL e Árvore de extensão · Veja mais »
Árvore de extensão mínima
Dado um grafo não orientado conectado, uma árvore de extensão deste grafo é um subgrafo o qual é uma árvore que conecta todos os vértices.
Novo!!: Complexidade SL e Árvore de extensão mínima · Veja mais »
Busca em largura
Na teoria dos grafos, busca em largura (ou busca em amplitude, também conhecido em inglês por Breadth-First Search - BFS) é um algoritmo de busca em grafos utilizado para realizar uma busca ou travessia num grafo e estrutura de dados do tipo árvore.
Novo!!: Complexidade SL e Busca em largura · Veja mais »
Busca em profundidade
Na teoria dos grafos, busca em profundidade (ou busca em profundidade-primeiro, também conhecido em inglês por Depth-First Search - DFS) é um algoritmo usado para realizar uma busca ou travessia numa árvore, estrutura de árvore ou grafo.
Novo!!: Complexidade SL e Busca em profundidade · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: Complexidade SL e Classe de complexidade · Veja mais »
Coloração de grafos
Em teoria dos grafos, coloração de grafos é um caso especial de rotulagem de grafos; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições.
Novo!!: Complexidade SL e Coloração de grafos · Veja mais »
Complemento (complexidade)
Na teoria da complexidade computacional, o complemento de um problema de decisão é o problema de decisão resultante do reverso das respostas sim e não.Igualmente, se definimos problemas de decisão como um conjunto de cadeias finitas, então o complemento deste conjunto sobre um domínio fixo é seu problema-complemento.
Novo!!: Complexidade SL e Complemento (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!!: Complexidade SL 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!!: Complexidade SL e Complexidade NL · Veja mais »
Conectividade st
Em ciência da computação e teoria da complexidade computacional, conectividade st é um problema de decisão onde dados os vértices s e t de um grafo direcionado, questiona-se se t é acessível partindo de s. Formalmente, o problema de decisão é dada por.
Novo!!: Complexidade SL e Conectividade st · Veja mais »
Endre Szemerédi
Endre Szemerédi (Budapeste) é um matemático húngaro.
Novo!!: Complexidade SL e Endre Szemerédi · Veja mais »
Grafo bipartido
No campo da matemática da teoria dos grafos, um grafo bipartido ou bigrafo é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V; ou seja, U e V são conjuntos independentes.
Novo!!: Complexidade SL e Grafo bipartido · Veja mais »
Grafo orientado
Um grafo orientado (direcionado). Um grafo orientado, grafo dirigido, grafo direcionado ou digrafo é um par G.
Novo!!: Complexidade SL e Grafo orientado · Veja mais »
Journal of the ACM
O Journal of the ACM (JACM) é a revista científica carro-chefe da Association for Computing Machinery (ACM).
Novo!!: Complexidade SL e Journal of the ACM · Veja mais »
L/Poly
Na teoria da complexidade computacional, L/poly é a classe de máquinas de espaço logarítmico com uma quantidade polinomial de palavras de aviso.
Novo!!: Complexidade SL e L/Poly · 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!!: Complexidade SL e LSPACE · 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!!: Complexidade SL e Máquina de Turing · 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!!: Complexidade SL e Máquina oráculo · Veja mais »
Máquinas de Turing Simétricas
Uma maquina de Turing simétrica é uma máquina de Turing que possui um grafo de configuração sem direção.
Novo!!: Complexidade SL e Máquinas de Turing Simétricas · Veja mais »
Omer Reingold
Omer Reingold (עומר ריינגולד) é um cientista da computação israelense.
Novo!!: Complexidade SL e Omer Reingold · Veja mais »
Ou exclusivo
Ou exclusivo ou disjunção exclusiva é uma operação lógica entre dois operandos que resulta em um valor lógico verdadeiro se e somente se os dois operandos forem diferentes, ou seja, se um for verdadeiro e o outro for falso.
Novo!!: Complexidade SL e Ou exclusivo · Veja mais »
Palavra de aviso
Na teoria de complexidade computacional, uma palavra de aviso é uma entrada adicional para uma Máquina de Turing que é permitida depender do comprimento de entrada n, mas não sobre a própria entrada. Um problema de decisão está na classe de complexidade P/f(n) se houver uma Máquina de Turing de tempo polinomial M com a seguinte propriedade: para qualquer n, há uma palavra de aviso A de comprimento f(n), de tal modo que, para qualquer entrada x de comprimento n, a máquina M decidi corretamente o problema da entrada x, dado x e A. A classe de complexidade mais comum envolvendo aviso é P/polinomial onde o comprimento do aviso f(n) pode ser qualquer polinômio em n. P/polinomial é igual ao problema de decisão de classes de tal modo que, para todo n, existe um Circuito booleano de tamanho polinomial decidindo corretamente o problema em todas as entradas de comprimento n. Uma direção da equivalência é fácil de ver.
Novo!!: Complexidade SL e Palavra de aviso · Veja mais »
Problema de satisfatibilidade booliana
Na teoria da complexidade computacional, o problema de satisfatibilidade booliana (do inglês boolean satisfiability problem, muitas vezes abreviado como SATISFIABILITY ou SAT) foi o primeiro problema identificado como pertencente à classe de complexidade NP-completo.
Novo!!: Complexidade SL e Problema de satisfatibilidade booliana · Veja mais »
Redução em espaço logarítmico
Na Teoria da Computação, uma redução em espaço logaritmico, é uma redução computável por uma maquina de Turing deterministica usando espaço logarítmico.
Novo!!: Complexidade SL e Redução em espaço logarítmico · Veja mais »
RL (complexidade)
Espaço Logarítmico Randomizado (RL), às vezes chamado de RLP (Espaço Logarítmico Randomizado de tempo Polinomial), é a classe de complexidade de problemas da teoria da complexidade computacional solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro unilateral.
Novo!!: Complexidade SL e RL (complexidade) · Veja mais »
Se e somente se
Se e somente se, ou se e só se (abreviado, sse), em matemática, lógica e filosofia, é uma forma de expressão para um teorema: Se A então B, e se B então A; ou A se e somente se B. O correspondente símbolo lógico é \Leftrightarrow.
Novo!!: Complexidade SL e Se e somente se · 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!!: Complexidade SL e Teorema de Savitch · Veja mais »
Teoria dos grafos
Grafo com quatro vértices e 6 arestas. É um grafo completo, conexo e planar. A teoria dos grafos ou de grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.
Novo!!: Complexidade SL e Teoria dos grafos · Veja mais »