Saltar para o conteúdo

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

Origem: Wikipédia, a enciclopédia livre.

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.

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 faculdade acha a 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 mão única
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.