Tese de Cobham

A Tese de Cobham, também conhecida como a tese de Cobham–Edmonds (assim denominada em referência a Alan Cobham e Jack Edmonds), assegura que problemas computacionais podem ser resolvidos de maneira viável em algum dispositivo de computação apenas se forem computáveis em tempo polinomial, ou seja, se pertencerem à classe de complexidade P.

3 relações: Complexidade computacional, Complexidade temporal, NC (complexidade).

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!!: Tese de Cobham e Complexidade computacional · Veja mais »

Complexidade temporal

Em ciência da computação, a complexidade temporal de um algoritmo quantifica o montante de tempo tomado por este dado algoritmo rodar como uma função do comprimento de uma cadeia representando os dados de entradaSipser, Michael (2006).

Novo!!: Tese de Cobham e Complexidade temporal · 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!!: Tese de Cobham e NC (complexidade) · Veja mais »

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