Problemas em aberto da ciência da computação – 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.

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.

• Lista de problemas em aberto
• Lista de problemas em aberto em física
• Lista de problemas em aberto em neurociência
• Lista de problemas em aberto em matemática
• Tese de Church-Turing
• Teste de Turing