¿Cuál es la complejidad del empaque rectangular cuando se permiten rotaciones?

En el problema de embalaje rectángulo, uno se le da un conjunto de rectángulos y que limitan rectángulo R . La tarea es encontrar una ubicación de r 1 , ... , r n dentro de R de manera que ninguno de los n rectángulos se superpongan. Generalmente, la orientación de cada rectángulo r i es fija. Es decir, los rectángulos no se pueden girar. En este caso, se sabe que el problema es NP completo (ver, p. Ej., Korp 2003 ).$\{r_1,\dots,r_n\}$$R$$r_1,\ldots,r_n$$R$$n$$r_i$

¿Cuál es la complejidad del problema de empaquetamiento de rectángulos si los rectángulos se pueden rotar grados?$90$

Intuitivamente, permitir rotaciones solo debería hacer que el problema sea más difícil, ya que primero se debe elegir una orientación para cada rectángulo y luego resolver el problema de empaquetamiento sin rotación. Pero la prueba de dureza NP del caso de no rotación es una reducción del empaquetamiento del contenedor y parece depender críticamente de la orientación fija de cada rectángulo para construir los contenedores. No he podido encontrar una prueba de dureza NP correspondiente para el caso en el que se permiten rotaciones.

Podemos reducir el problema de empaque sin rotaciones al problema de empaque con rotaciones permitidas de la siguiente manera. Tome cualquier instancia del problema de no rotación. Verticalmente escala toda la instancia por el doble de la relación de la anchura más pequeña de cualquier rectángulo r i dividida por la altura del rectángulo recipiente R . (Esta relación tiene un número polinómico de bits, por lo que la transformación se puede ejecutar en tiempo polinómico). Cada rectángulo escalado r $(R, r_1, r_2, \dots, r_n)$$r_i$$R$ encaja dentro del contenedor a escala R $r'\!\!_i$$R'$ sólo en su orientación original, por lo que permite rotaciones no añade nuevas soluciones.