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.
Índice |
[editar] P=NP
- 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 (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.
[editar] A existência de funções de um sentido
- 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.
