Que connaît-on comme problèmes (si possible « naturels ») qui soient dans NP et co- NP mais n'aient pas été prouvés dans P ? (Dans le temps, il y a eu la programmation linéaire et la primalité, mais dans les deux cas on a des algorithmes P.)