Por lo tanto si ambas definiciones de la NP-completitud son iguales hay un problema co-NP-completo (bajo ambas definiciones) como por ejemplo el complementario del problema de la satisfacibilidad booleana que es también NP-completo (bajo ambas definiciones).