Problemas em aberto da ciência da computação

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Este artigo é uma lista de problemas em aberto na Ciência da computação. A solução de tais problemas trará grande impacto para o campo de estudo a qual pertencem.

P=NP[editar | editar código-fonte]

Campo 
Teoria da computação
Artigo 
P versus NP
Fonte 
S. A. Cook e Leonid Levin, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing ou Procedimentos do 3º Sympósio Anual ACM da Teoria da Computação. (1971), pp. 151--158.
Descrição 
P é uma classe de problemas cuja solução pode ser encontrada em tempo polinomial. NP é uma classe de problemas cuja solução pode ser encontrada em tempo polinomial com um algoritmo não determinístico ou, equivalentemente, cuja solução pode ser verificada de forma determinística em tempo polinomial. Naturalmente, todo problema P é também NP. A questão "P versus NP" é se NP é um sub-conjunto de P, isto é, se ambas as classes são iguais.
Importância 
Se as classes são iguais então pode-se resolver problemas que, atualmente, consideram-se intratáveis.
Conjectura 
apesar da questão estar longe de ser resolvida por completo, a maioria dos especialistas acredita que as classes são diferentes.

A existência de funções de um sentido[editar | editar código-fonte]

Campo 
Criptografia
Artigo 
Função de um sentido
Fonte 
W.Diffie, M.E.Hellman, IEEE Trans. Inform. Theory, IT-22, 6, 1976, pp.644-654 [1]
Descrição 
Funções de um sentido são aquelas cuja computação é simples mas cuja inversão é difícil. Apesar de existirem diversos candidatos com nenhum algoritmo inverso adequado conhecido, nunca foi provado que tais funções não existem.
Importância 
Se as funções de um sentido não existem então a criptografia de chave pública é impossível. Sua existência implicaria que várias classes de complexidade não podem ser aprendidas, e que P ≠ NP.
Conjectura 
É assumido mas não provado que tais funções existem. Vários sistemas de criptografia são baseados na crença que a modulação exponencial é uma função de um sentido.

Referências[editar | editar código-fonte]

Ver também[editar | editar código-fonte]