Lista de problemas fuertemente NP-hard con datos numéricos

Estoy buscando problemas NP-hard para una reducción. Hasta ahora he encontrado los siguientes problemas:

• Problema de 3 particiones
• problema de embalaje
• Emparejamiento numérico tridimensional
• TSP
• Cualquier problema de NP completo sin datos numéricos, por ejemplo, SATISFIABILIDAD, CICLO HAMILTONIANO, 3-COLOURABILIDAD.

¿Alguien sabe de una lista de problemas fuertemente NP-hard?

Si no, construyamos uno aquí. ¿Conoce otros problemas con los datos numéricos que son fuertemente NP-hard?

Estoy particularmente interesado en problemas fuertemente NP-duros en gráficos ponderados.

Aquí hay una fuerte -Complete$NP$ problema (con datos numéricos como usted pidió):

Problema de Schur Triples :

Entrada: lista de 3N enteros positivos distintos

Pregunta: ¿Hay una partición de la lista en N triples modo que para cada triple ?a i + b i = c i$(a_i, b_i, c_i)$$a_i + b_i= c_i$$i$

La condición de que todos los números deben ser distintos hace que el problema sea muy interesante y McDiarmid lo llama sorprendentemente problemático .

Mientras pensaba en posibles respuestas, se me ocurrió este simple problema numérico fuertemente NP-completo:

PRODUCTO DE SUBSET GRATIS CUADRADO: Dados enteros, encuentre de ellos cuyo producto esté libre de cuadrados.$3N$$N$

Boceto de prueba: a partir de una cubierta Exact por 3 sets (X3C) instancia (fuertemente NPC) etiquete cada elemento del universo con un primo distinto (puede generar de ellos en tiempo polinómico); luego convierta cada triple de los subconjuntos a .( x , y , z ) x y $3|X|$$(x,y,z)$$xyz$

No lo encontré en ningún lado, por lo que puede ser algo "original".

Obviamente se asemeja al PRODUCTO SUBSET mejor conocido (que no es fuertemente NPC debido a la presencia del producto objetivo , ver David S. Johnson: The NP-Completeness Column: An Continuing Guide. 393-405).$B$

También se puede piratear un poco para obtener otras variantes, como:

• Dados los enteros , encuentre de ellos cuyo producto sea una potencia perfecta número ;N $3N$$N$$21$
• Dados enteros, encuentre un subconjunto cuyo producto sea el 3N-ésimo primorial. (tipo de trampa :-)$N$

Cieliebak en su Ph.D. Disertación demostró varios problemas para ser NP-completo. Específicamente, el problema del resumen doble y el problema de k-Equal Sum Subsets (cuando ) son fuertemente completos.N $k= \Omega(n)$$NP$

Aquí hay otro fuerte: desde el dominio de la programación teórica y la optimización combinatoria, el problema de makepan en máquinas paralelas idénticas (denotado comúnmente como en la literatura). Tenga en cuenta que algunos de los problemas de programación más difíciles casi todos tienen esto como un caso especial (por ejemplo, el problema de makepan en máquinas paralelas no relacionadas). P | El | C m a $NP$$P||C_{max}$

Es fuertemente duro, porque puede reducir el problema de partes (consulte http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec10.pdf sección 10.5).$NP$$3$

¡Espero que esto ayude!