Para mostrar la dureza NP de un problema, uno necesita elegir un problema NP-duro conocido y encontrar una reducción polinómica del problema conocido a su problema en cuestión. Teóricamente, cualquier problema NP-duro puede usarse para la reducción, pero en la práctica, algunos de los problemas se reducen más fácilmente que otros.
Por ejemplo, 3-SAT suele ser una mejor opción para construir una reducción que SAT porque el primero es más restringido que el último, 3-partición suele ser una opción más fácil que el embalaje de contenedores, ...
Una forma de encontrar esos problemas "buenos" para la reducción es hacer un análisis estadístico sobre las reducciones existentes. Por ejemplo, uno puede dar forma a todos los pares de from -> toreducciones del libro Computadoras e Intractabilidad: una guía para la teoría de la completitud NP
(u otros recursos) y dibujar un histograma de los problemas en el fromconjunto. Entonces podemos descubrir qué problemas se usan más comúnmente para las reducciones.
Me pregunto si ese análisis estadístico tiene sentido. ¿Se ha llevado a cabo tal investigación o no? Si no, ¿cuál es su suposición sobre los problemas más utilizados para las reducciones?
La razón por la que hago esta pregunta es que ya he hecho algunas pruebas de dureza NP, pero casi todas dependen de la reducción del mismo problema (3 particiones). Estoy buscando otras opciones para usar en mis pruebas.
fuente
Respuestas:
No sé si hay una forma de maquinaria para hacer esto, pero mi pequeña experiencia personal funciona de la siguiente manera.
Intento proporcionar un algoritmo de tiempo polinómico para un problema. En esos intentos, por lo general, puedo ver que hay algunas versiones restringidas del problema que pueden resolverse en tiempo polinómico. También entenderé qué parte de mi algoritmo se movía a mano para el problema original. Puedo comparar estos dos casos (la diferencia entre las versiones restringidas y la general también es parte de un algoritmo que fue difícil de mejorar). Al comparar estos dos casos, generalmente es posible adivinar cómo se ve el problema del cuello de botella. Entonces podemos encontrar un problema difícil relacionado. Por lo general, proporcionar un algoritmo para un problema es un trabajo difícil y necesita un buen conocimiento sobre un problema. Después de obtener este conocimiento sobre el problema, podemos tener muchas ideas diferentes para abordar el problema en diferentes escenarios (no solo resultados de dureza).
PD: Si tu prueba se basa en un problema en particular, creo que es porque ese problema está muy cerca de tu trabajo, así que no te culpes.
fuente