Problemas de Detección de Fallos Completos Polinómicamente

Examinamos varias variaciones del problema de detección de un solo fallo para circuitos lógicos combinacionales y mostramos que decidir si los fallos individuales son detectables mediante experimentos de entrada-salida (I/O) es polinómicamente completo, es decir, hay un algoritmo en tiempo polinómico para decidir si estos fallos individuales son detectables si y solo si hay un algoritmo en tiempo polinómico para problemas como el problema del vendedor viajero, el problema de la mochila, etc.