Quelle est la complexité de l'emballage rectangle lorsque les rotations sont autorisées?

Dans le problème de l' emballage de rectangle, on se donne un ensemble de rectangles et délimitant rectangle . La tâche consiste à trouver un emplacement de intérieur de sorte qu'aucun des rectangles ne se chevauche. Généralement, l'orientation de chaque rectangle est fixe. Autrement dit, les rectangles ne peuvent pas être tournés. Dans ce cas, le problème est connu pour être NP-complet (voir, par exemple, Korp 2003 ).$\{r_1,\dots,r_n\}$$R$$r_1,\ldots,r_n$$R$$n$$r_i$

Quelle est la complexité du problème d'emballage de rectangle si les rectangles peuvent être tournés de degrés?$90$

Intuitivement, autoriser les rotations ne devrait que rendre le problème plus difficile, car il faut d'abord choisir une orientation pour chaque rectangle, puis résoudre le problème d'emballage sans rotation. Mais la preuve de dureté NP du boîtier sans rotation est une réduction par rapport à l'emballage des bacs et semble dépendre de façon critique de l'orientation fixe de chaque rectangle afin de construire les bacs. Je n'ai pas pu trouver une preuve de dureté NP correspondante pour le cas où les rotations sont autorisées.

Nous pouvons réduire le problème d'emballage sans rotation au problème d'emballage autorisé par rotations comme suit. Prenez n'importe quelle instance du problème de non-rotation. L' échelle verticalement l'instance entière par deux fois le rapport de la plus petite largeur d'un rectangle quelconque r i divisé par la hauteur du rectangle de récipient R . (Ce rapport a un nombre polynomial de bits, donc la transformation peut être exécutée en temps polynomial.) Chaque rectangle à l'échelle r $(R, r_1, r_2, \dots, r_n)$$r_i$$R$$r'\!\!_i$$R'$