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
Alguém consegue provar que algum problema dado explicitamente precisa de circuitos booleanos de tamanho maior que linear? O melhor limite inferior conhecido é de apenas cerca de 4n.
NP é diferente de co-NP? De forma equivalente, não existe nenhum sistema de prova com provas curtas de todas as tautologias?
Que técnicas de prova conseguem superar as barreiras conhecidas da «relativização» e das «provas naturais»?