Terra Incognita
Matemática

P é igual a NP?

Horizonte distante

Por que isso importa

Pergunta se todo o problema cuja resposta é fácil de verificar também é fácil de resolver. Se for, os transportes poderiam ser planeados de forma ótima, levando pessoas e mercadorias mais depressa e mais barato, mas a criptografia de chave pública tornar-se-ia impossível.

O que sabemos

Formulado em 1971: se um problema é fácil de verificar, ele também é fácil de resolver?

O que nos trava

Várias famílias importantes de técnicas de demonstração se mostraram insuficientes.

Pistas atuais

Teoria da complexidade geométrica, limites inferiores para circuitos.

Subperguntas

Perguntas relacionadas

Fontes

Ainda não revisado por um especialista.

Última verificação: 2026-11-18

Histórico desta pergunta

Voltar ao mapa →