Aunque la cuestión de si NP = co-NP es una pregunta abierta se considera muy poco probable porque también es muy poco probable que las dos definiciones de NP-completitud sean equivalentes.