Linguagem esparsa e NP-completo

Atalhos: Diferenças, Semelhanças, Coeficiente de Similaridade de Jaccard, Referências.

Diferença entre Linguagem esparsa e NP-completo

Linguagem esparsa vs. NP-completo

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. 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.

Semelhanças entre Linguagem esparsa e NP-completo

Linguagem esparsa e NP-completo têm 6 coisas em comum (em Unionpedia): Complexidade computacional, NP (complexidade), P (complexidade), P versus NP, P-completo, Redução em tempo polinomial.

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.

Complexidade computacional e Linguagem esparsa · Complexidade computacional e NP-completo · 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.

Linguagem esparsa e NP (complexidade) · NP (complexidade) 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.

Linguagem esparsa e P (complexidade) · NP-completo e P (complexidade) · Veja mais »

P versus NP

O problema "P versus NP" é o principal problema aberto da Ciência da Computação.

Linguagem esparsa e P versus NP · NP-completo e P versus NP · Veja mais »

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.

Linguagem esparsa e P-completo · NP-completo e P-completo · Veja mais »

Redução em tempo polinomial

Na teoria da complexidade computacional uma redução em tempo polinomial é uma redução que é computável por uma máquina de turing determinística em tempo polinomial.

Linguagem esparsa e Redução em tempo polinomial · NP-completo e Redução em tempo polinomial · Veja mais »

A lista acima responda às seguintes perguntas

O que têm em comum Linguagem esparsa e NP-completo
Quais são as semelhanças entre Linguagem esparsa e NP-completo

Comparação entre Linguagem esparsa e NP-completo

Linguagem esparsa tem 17 relações, enquanto NP-completo tem 41. Como eles têm em comum 6, o índice de Jaccard é 10.34% = 6 / (17 + 41).

Referências

Este artigo é a relação entre Linguagem esparsa e NP-completo. Para acessar cada artigo visite:

Unionpédia é um mapa conceitual ou rede semântica organizado sob a forma de enciclopédia - dicionário. Dá uma breve definição de cada conceito e toda a sua relacionados.

É um mapa mental on-line gigante que serve de base para os diagramas de conceito. É livre para usar e cada artigo ou documento pode ser baixado. É uma ferramenta, de recursos ou de referência para estudo, pesquisa, educação, ou formação, eles podem usar professores, educadores, alunos e estudantes; ou para o mundo acadêmico: para a escola, primário, secundário, médio, faculdade, grau técnico, universidade, graduação, mestrado ou doutorado; para papéis, relatórios, documentos, projetos, idéias, documentação, resumos, pesquisas ou teses. Aqui aparece a definição, explicação, descrição, ou o significado de cada significativa no qual você precisa de informações e uma lista de seus conceitos associados como um glossário. Disponível em português, inglês, espanhol, japonês, chinês, francês, alemão, italiano, polonês, holandês, russo, árabe, hindi, sueco, ucraniano, húngaro, catalão, checo, hebraico, dinamarquês, finlandês, indonésio, norueguês, romeno, turco, vietnamita, coreano, tailandês, grego, búlgaro, croata, eslovaco, lituano, filipino, letão, estoniano e esloveno. Mais idiomas em breve.

Todas as informações foi feita a partir de Wikipédia, é disponibilizado nos termos da licença Creative Commons - Atribuição - Compartilha Igual 3.0 Não Adaptada (CC BY-SA 3.0).

A Unionpédia não é endossada ou afiliada à Wikimedia Foundation.

Google Play, Android e o logotipo do Google Play são marcas registradas da Google Inc.

Política de Privacidade