Esto se demuestra como sigue: Si hubiera un problema en NP-completo y en co-NP al mismo tiempo, todo problema de NP se reduciría en él, se deduce que para todo problema en NP se podría construir una máquina de Turing no determinista que decidiera el problema complementario en tiempo polinómico, es decir, NP sería un subconjunto de co-NP y, por tanto los complementos de NP serían subconjunto de los complementos de co-NP, es decir, co-NP sería un subconjunto de NP, Por tanto NP y co-NP serían el mismo conjunto.