Logotipo
Unionpédia
Comunicação
Disponível no Google Play
Novo! Faça o download do Unionpédia em seu dispositivo Android™!
Instalar
Acesso mais rápido do que o navegador!
E sem anúncios!

P-completo

Na teoria da complexidade computacional, a noção de problema de decisão P-completo é útil na análise de questões como.

24 relações: Algoritmo de Euclides estendido, Busca em profundidade, Cálculo lambda, Cláusula de Horn, Complexidade computacional, Exptime, Fatoração, Gramática livre de contexto, Gzip, Jogo da vida, Linguagem esparsa, LSPACE, LZW, Máquina de Turing, Máximo divisor comum, NC (complexidade), NP (complexidade), NP-completo, P (complexidade), Problema de decisão, Problema de satisfatibilidade booliana, Programação linear, Sistema de numeração binário, Teoria dos grafos.

Algoritmo de Euclides estendido

O Algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides, que, além de calcular o máximo divisor comum (MDC) entre a, b \in \mathbb, fornece os coeficientes \alpha, \beta \in \mathbb tais que \alpha a + \beta b.

Novo!!: P-completo e Algoritmo de Euclides estendido · 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!!: P-completo e Busca em profundidade · Veja mais »

Cálculo lambda

Na lógica matemática e na ciência da computação, lambda cálculo, também escrito como cálculo-λ é um sistema formal que estuda funções recursivas computáveis, no que se refere a teoria da computabilidade, e fenômenos relacionados, como variáveis ligadas e substituição.

Novo!!: P-completo e Cálculo lambda · Veja mais »

Cláusula de Horn

Em lógica, uma cláusula de Horn é uma cláusula (disjunção de literais) com no máximo um literal positivo.

Novo!!: P-completo e Cláusula de Horn · 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!!: P-completo e Complexidade computacional · 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!!: P-completo e Exptime · Veja mais »

Fatoração

(AO 1945: Factorização) é o termo usado na álgebra para designar a decomposição que se faz de cada um dos elementos que integram um produto, ou seja, o resultado de uma multiplicação.

Novo!!: P-completo e Fatoração · Veja mais »

Gramática livre de contexto

A gramatica livre de contexto (GLC), em teoria de linguagem formal, é uma gramática formal onde todas as regras de produções são da forma A\ \to\ \alpha Onde A é um símbolo não terminal, e \alpha  é uma cadeia de terminal e/ou não terminais (\alpha pode ser vazia). Uma linguagem formal é considerada “livre do contexto” quando suas regras de produções podem ser aplicadas independentemente do contexto do simbolo não terminal.

Novo!!: P-completo e Gramática livre de contexto · Veja mais »

Gzip

gzip é um tanto um software para compactação de arquivos que serve de implementação de referência quanto o formato do arquivo compactado que este gera.

Novo!!: P-completo e Gzip · Veja mais »

Jogo da vida

thumb Gosper'' criando ''planadores''. O jogo da vida é um autómato celular desenvolvido pelo matemático britânico John Horton Conway em 1970.

Novo!!: P-completo e Jogo da vida · Veja mais »

Linguagem esparsa

Em teoria da complexidade computacional, uma linguagem esparsa é uma linguagem formal (um conjunto de strings) cujo número de strings de comprimento n na língua é limitada por uma função de polinômio n. São utilizadas principalmente no estudo da relação entre a classe de complexidade NP com outras classes.

Novo!!: P-completo e Linguagem esparsa · 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!!: P-completo e LSPACE · Veja mais »

LZW

LZW (Lempel-Ziv-Welch) é um algoritmo de compressão de dados, derivado do algoritmo LZ78, baseado na localização e no registro das padronagens de uma estrutura.

Novo!!: P-completo e LZW · 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!!: P-completo e Máquina de Turing · Veja mais »

Máximo divisor comum

O máximo divisor comum (abreviadamente, MDC) entre dois ou mais números inteiros é o maior número inteiro que é fator de tais números.

Novo!!: P-completo e Máximo divisor comum · 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!!: P-completo e NC (complexidade) · 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!!: P-completo 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!!: P-completo 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!!: P-completo e P (complexidade) · 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!!: P-completo e Problema de decisão · Veja mais »

Problema de satisfatibilidade booliana

Na teoria da complexidade computacional, o problema de satisfazibilidade booleana (SAT) foi o primeiro problema identificado como pertencente à classe de complexidade NP-completo.

Novo!!: P-completo e Problema de satisfatibilidade booliana · Veja mais »

Programação linear

Exemplo de poliedro (bidimensional) resultante das condições de um problema de programação linear. Em matemática, problemas de Programação Linear (PL) são problemas de optimização nos quais a função objetivo e as restrições são todas lineares.

Novo!!: P-completo e Programação linear · Veja mais »

Sistema de numeração binário

O sistema binário ou de base 2 é um sistema de numeração posicional em que todas as quantidades se representam com base em dois números, ou seja, zero e um (0 e 1).

Novo!!: P-completo e Sistema de numeração binário · Veja mais »

Teoria dos grafos

Grafo com 4 vértices e 6 arestas. É um grafo completo, conexo e planar. A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.

Novo!!: P-completo e Teoria dos grafos · Veja mais »

CessanteEntrada
Ei! Agora estamos em Facebook! »