Resumen:
En esta tesis se define el concepto de clase difícil, como una relación
de pre-orden que permite relacionar clases de instancias pertenecientes a un problema de decisión dado. Mientras más difícil sea una clase utilizada como dominio de aplicación en un plan de testing para un algoritmo, más confiables resultar an las conclusiones a las que lleguemos acerca de la eficiencia de ese algoritmo.
En particular, se definen y caracterizan clases difíciles para el problema
de completitud de hipergrafos, así como para el problema de completitud restringido a pares coherentes; algunas de estas clases ya eran conocidas en la literatura, y otras son propias de este trabajo. Además se demuestra que los benchmark utilizados en la práctica por los algoritmos que resuelven este problema no son estrictamente difí ciles, y se de ne una nueva subclase de este
tipo, la de los pares triangulares, perteneciente a una clase muy difí cil, que
se presenta como un benchmark exigente (aunque no su ciente), no utilizado
hasta ahora.
Finalmente, se describen algunos mecanismos para ayudar a generar pares
de hipergrafos pertenecientes a clases difíciles, y se indaga acerca de las
dificultades para la realización de esta tarea.