Esta investigación tiene como objetivo explicar la dificultad intrínseca de la lista de veintiún problemas de Karp a través del uso de medidas de complejidad empírica basadas en el ancho elipsoidal del politopo generado por las restricciones del problema de programación lineal relajado. Las variables utilizadas como medidas de complejidad son el número de nodos visitados y el tiempo de CPU empleado en resolver los problemas. Las mediciones utilizadas como variables explicativas corresponden a los autovalores de la elipse de Dikin dentro del politopo. Otras variables corresponden al margen de restricción con respecto al centro analítico utilizado como centro de la elipse. Los resultados de estas variables en términos del número de nodos y tiempo de CPU son particularmente satisfactorios. Muestran correlaciones fuertes, por encima del 60%, en la mayoría de los casos.